Лекция по информатике "Алгебра логики"

10

Лекция № 6

Алгебра логики. Основные логические операции.

Построение таблиц истинности сложных высказываний

1. Формы мышления

Первые учения о формах и способах рассуждений возникли в странах древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания.

Логика – это наука о формах и способах мышления.

Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны.

Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются:

1) Понятие

Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.

Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов.

Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер — это устройство для автоматической обработки информации, предназначенное для одного пользователя».

Объем понятия определяется совокупностью предметов, на которые оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

2) Высказывание

Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними. Высказывание может быть либо истинно, либо ложно (5 + 3 = 8 – истинное высказывание; Лондон является столицей Франции – ложное высказывание).

Высказывание не может быть выражено повелительным, восклицательным, или вопросительным предложением, т. к. оценка их истинности или ложности невозможна.

На основании простых высказываний могут быть построены составные высказывания. Например, высказывание «Процессор является устройством обработки информации и принтер является устройством печати» является составным высказыванием, состоящим из двух простых.

Если истинность или ложность простых высказываний устанавливается в результате соглашения на основании здравого смысла, то истинность или ложность составных высказываний вычисляется с помощью использования алгебры высказываний.

Приведенное выше составное высказывание истинно, т.к. истинны, входящие в него простые высказывания.

3) Умозаключение

Умозаключение — это форма мышления с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (вывод).

Посылками умозаключения по правилам формальной логики могут быть только истинные суждения. Тогда, если умозаключение проводится в соответствии с правилами формальной логики, то оно будет истинным. В противном случае, можно придти к ложному умозаключению.

2. Понятие об алгебре высказываний

Алгебра логики – математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Употребляемые в обычной речи слова «не», «и», «или», «если …, то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

Высказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называют элементарными.

В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые заглавными буквами латинского алфавита. Рассмотрим два простых высказывания:

А — «два умножить на два равно четырем»,

В — «два умножить на два равно пяти».

Высказывания, как уже говорилось ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).

В алгебре высказываний высказывания обозначаются именами логических переменных которые могут принимать лишь два значения «истина» (1) и «ложь» (0).

В алгебре высказываний над высказываниями можно производить определенные логические операции, в результате которых получаются новые, составные высказывания.

Для образования новых высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: «1» и «0».

Из этого следует два вывода:

1. одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных;

2. на этапе конструирования аппаратных средств алгебры логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера.

Существуют различные физические способы кодирования двоичной информации, но чаще всего единица кодируется более высоким уровнем напряжения, чем ноль.

3. Основные логические операции

Логическое умножение (конъюнкция)

Объединение двух (или нескольких) высказываний в одно с помощью союза «и называется операцией логического умножения или конъюнкцией.

Составное высказывание, образованное в результате операции логического умножения (конъюнкции), истинно тогда и только тогда, когда истинны входящие в него простые высказывания.

Так, из приведенных ниже четырех составных высказываний, образованных с помощью операции логического умножения, истинно только четвертое, так как в первых трех составных высказываниях хотя бы одно из простых высказываний ложно:

Перейдем теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). Операцию логического умножения (конъюнкцию) принято обозначать либо значками «&», «» либо знаком умножения «*». Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний:

С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами которой являются логические переменные А и В, которые могут принимать значения «истина» (1) и «ложь» (0).

Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов.

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2х2=4 и 3х3=10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение ложь (F = 0), т.е. данное составное высказывание ложно.

А	В
1	1	1
1	0	0
0	1	0
0	0	0

Логическое сложение (дизъюнкция)

Объединение двух (или нескольких) высказываний с помощью союза «или» называется операцией логического сложения или дизъюнкцией.

Составное высказывание, образованное в результате логического сложения (дизъюнкции), истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.

Так, из приведенных ниже четырех составных высказываний, образованных с помощью операции логического сложения, ложно только первое, так как в последних трех составных высказываниях хотя бы одно из простых высказываний истинно:

Запишем теперь операцию логического сложения на формальном языке алгебры логики. Операцию логического сложения (дизъюнкцию) принято обозначать либо значком «» либо знаком сложения «+». Образуем составное высказывание F, которое получится в результате дизъюнкции двух простых высказываний:

С точки зрения алгебры высказываний мы записали формулу функции логического сложения, аргументами которой являются логические переменные А и В. Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает какие значения принимает логическая функция при всех возможных наборах ее аргументов.

По таблице истинности легко определить истинность составного высказывания образованного с помощью операции логического сложения. Рассмотрим, например, составное высказывание «2х2=4 или 3х3=10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение истина (F = 1), т.е. данное составное высказывание истинно.

А	В
1	1	1
1	0	1
0	1	1
0	0	0

Логическое отрицание (инверсия)

Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.

Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное — истинным.

Пусть А = «Два умножить на два равно четырем» - истинное высказывание, тогда высказывание F, образованное с помощью операции логического отрицания, «Два умножить на два не равно четырем» -ложно.

Операцию логического отрицания (инверсию) над логическим высказыванием А принято обозначать . Образуем высказывание F, являющееся логическим отрицанием А.

Истинность такого высказывания задается таблицей истинности функции логического отрицания.

Истинность высказывания, образованного с помощью операции логического отрицания, можно легко определить с помощью таблицы истинности. Например, высказывание «Два умножить на два не равно четырем» ложно (А = 0), а полученное из него в результате логического отрицания высказывание «Два умножить на два равно четырем» истинно (F = 1).

А
1	0
0	1

Логическое следование (импликация)

А	В
1	1	1
1	0	0
0	1	1
0	0	1

Логическое равенство (эквиваленция)

А	В
1	1	1
1	0	0
0	1	0
0	0	1

Порядок следования логических операций

отрицание (, конъюнкция (, дизъюнкция (, импликация (, эквиваленция (

4. Логические выражения и таблицы истинности.

Построение таблиц истинности составных высказываний

Каждое составное высказывание можно выразить в виде формулы (логического выражения), в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции.

Для записи составных высказываний в виде логических выражений на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними.

Запишем в форме логического выражения составное высказывание «2х2=5 или 2х2=4 и 2х25 или 2х24». Проанализируем составное высказывание. Оно состоит из двух простых высказываний:

А = «2х2=5» - ложно (0),

В = «2х2=4» - истинно (1).

Тогда составное высказывание можно записать в следующей форме:

Теперь необходимо записать высказывание в форме логического выражения с учетом последовательности выполнения логических операций. При выполнении логических операций определен следующий порядок их выполнения: инверсия, конъюнкция, дизъюнкция. Для изменения указанного порядка могут использоваться скобки.

Истинность или ложность составных высказываний можно определять чисто формально, руководствуясь законами алгебры высказываний, не обращаясь к смысловому содержанию высказываний.

Подставим в логическое выражение значения логических переменных и, используя таблицы истинности базовых логических операций, получим значение логической функции:

Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет его истинность или ложность при всех возможных комбинациях исходных значений простых высказываний (логических переменных).

При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий.

Во-первых, необходимо определить количество строк в таблице истинности, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение. Если количество логических переменных n, то:

В нашем случае логическая функция имеет две переменные и, следовательно, количество строк в таблице истинности должно быть равно 4.

Во-вторых, необходимо определить количество столбцов в таблице истинности, которое равно количеству логических переменных плюс количество логических операций. В нашем случае количество переменных равно двум, а количество логических операций равно пяти, т.е. количество столбцов таблицы истинности равно семи.

В-третьих, необходимо построить таблицу истинности с указанным количеством строк и столбцов, обозначить столбцы и внести возможные наборы значений исходных логических переменных.

В-четвертых, необходимо заполнить таблицу истинности по столбцам, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности. Теперь мы можем определить значение логической функции для любого набора значений логических переменных.

Логические выражения, у которых таблицы истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак «=».

Докажем, что логические выражения равносильны. Построим сначала таблицу истинности для логического выражения .

Построим теперь таблицу истинности для логического выражения .

Таблицы истинности совпадают, следовательно, логические выражения равносильны:

Итак, чтобы составить таблицу истинности для логической формулы, надо выполнить следующие шаги:

1. подсчитать количество переменных n в логическом выражении

2. определить число строк в таблице, которое равно Q = 2ⁿ

3. подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций

4. ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учётом скобок и приоритетов

5. заполнить столбцы входных переменных наборами значений

6. провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п. 4 последовательностью.

Переменные			Промежуточные логические формулы					Формула
x	y	z
0	0	0	1	1	0	1	0	0
0	0	1	1	1	0	1	1	1
0	1	0	0	0	1	1	0	1
0	1	1	0	0	1	1	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	0	0	0
1	1	0	0	1	0	0	0	0
1	1	1	0	1	0	0	0	0

Пример (см. выше):

Данная формула является выполнимой, так как в некоторых случаях принимает значение «истина», а в некоторых – «ложь».