Лекция по информатике "Алгебра логики"
Данная лекция содержит подробное описание алгебры логики. Даются и раскраываются полные определения, приводятся примеры. Рассматриваются понятия которые не входят в курсс информатики школы. Даёться полное представления о логических операциях. думаю что данная лекция поможет в работе как начинающему специалисту так и стажисту.
Просмотр содержимого документа «Лекция по информатике "Алгебра логики" »Алгебра логики. Основные логические операции.
Построение таблиц истинности сложных высказываний
1. Формы мышления
Первые учения о формах и способах рассуждений возникли в странах древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания.
Логика – это наука о формах и способах мышления.
Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны.
Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются:
Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.
Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов.
Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер — это устройство для автоматической обработки информации, предназначенное для одного пользователя».
Объем понятия определяется совокупностью предметов, на которые оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.
2) Высказывание
Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними. Высказывание может быть либо истинно, либо ложно (5 + 3 = 8 – истинное высказывание; Лондон является столицей Франции – ложное высказывание).
Высказывание не может быть выражено повелительным, восклицательным, или вопросительным предложением, т. к. оценка их истинности или ложности невозможна.
На основании простых высказываний могут быть построены составные высказывания. Например, высказывание «Процессор является устройством обработки информации и принтер является устройством печати» является составным высказыванием, состоящим из двух простых.
Если истинность или ложность простых высказываний устанавливается в результате соглашения на основании здравого смысла, то истинность или ложность составных высказываний вычисляется с помощью использования алгебры высказываний.
Приведенное выше составное высказывание истинно, т.к. истинны, входящие в него простые высказывания.
3) Умозаключение
Умозаключение — это форма мышления с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (вывод).
Посылками умозаключения по правилам формальной логики могут быть только истинные суждения. Тогда, если умозаключение проводится в соответствии с правилами формальной логики, то оно будет истинным. В противном случае, можно придти к ложному умозаключению.
2. Понятие об алгебре высказываний
Алгебра логики – математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.
Создателем алгебры логики является английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Употребляемые в обычной речи слова «не», «и», «или», «если …, то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.
Высказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называют элементарными.
В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые заглавными буквами латинского алфавита. Рассмотрим два простых высказывания:
А — «два умножить на два равно четырем»,
В — «два умножить на два равно пяти».
Высказывания, как уже говорилось ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).
В алгебре высказываний высказывания обозначаются именами логических переменных которые могут принимать лишь два значения «истина» (1) и «ложь» (0).
В алгебре высказываний над высказываниями можно производить определенные логические операции, в результате которых получаются новые, составные высказывания.
Для образования новых высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».
Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: «1» и «0».
Из этого следует два вывода:
одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных;
на этапе конструирования аппаратных средств алгебры логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера.
Существуют различные физические способы кодирования двоичной информации, но чаще всего единица кодируется более высоким уровнем напряжения, чем ноль.
3. Основные логические операции
Логическое умножение (конъюнкция)
Объединение двух (или нескольких) высказываний в одно с помощью союза «и называется операцией логического умножения или конъюнкцией.
Составное высказывание, образованное в результате операции логического умножения (конъюнкции), истинно тогда и только тогда, когда истинны входящие в него простые высказывания.
Так, из приведенных ниже четырех составных высказываний, образованных с помощью операции логического умножения, истинно только четвертое, так как в первых трех составных высказываниях хотя бы одно из простых высказываний ложно:
Перейдем теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). Операцию логического умножения (конъюнкцию) принято обозначать либо значками «&», « » либо знаком умножения «*». Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний:
С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами которой являются логические переменные А и В, которые могут принимать значения «истина» (1) и «ложь» (0).
Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов.
По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2х2=4 и 3х3=10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение ложь (F = 0), т.е. данное составное высказывание ложно.