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

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

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

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

А = «2 • 2 = 5» — ложно (0), В = «2 • 2 = 4» — истинно (1).

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

«(А или В) и (А или В)».

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

F = (А v В) & (А v В).

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

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

F = (А v В)&(А v В) = (О v 1)&(1 v 0) = 1 & 1 = 1.

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

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

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

В нашем случае логическая функция F — (АvВ)&(АvВ) имеет 2 переменные и, следовательно, количество строк в таблице истинности должно быть равно 4.

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

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

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

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

Таблица 3.4. Таблица истинности логической функции

A	B	АvВ	!А	!В	!(AvВ)	(АvВ)&(АvВ)
0	0	0	1	1	1	0
0	1	1	1	0	1	1
1	0	0	0	1	1	1
1	1	1	0	0	0	0

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

Докажем, что логические выражения !(А & В) и !(АvВ) равносильны. Построим сначала таблицу истинности логического выражения А & В (табл. 3.5).

Таблица 3.5. Таблица истинности логического выражения А & В

A	B	!A	!B	!(А&В)
0	0	1	1	1
0	1	1	0	0
1	0	0	1	0
1	1	0	0	0

Теперь построим таблицу истинности логического выражения АvВ (табл. 3.6).

Таблица 3.6. Таблица истинности логического выражения АvВ

A	B	АVВ	!(АvВ)
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

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

!(А&В) = !(АvВ).

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

Логическая операция импликации «если А, то В», обозначается А -> В и выражается с помощью логической функции F14, которая задается соответствующей таблицей истинности (табл. 3.8).

Таблица 3.8. Таблица истинности логической функции «импликация»

A	B	F14 = A->В
0	0	1
0	1	1
1	0	0
1	1	1

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

Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, так как истинны и первое высказывание (предпосылка), и второе высказывание (вывод).

Высказывание «Если число делится на 10, то оно делится на 3» ложно, так как из истинной предпосылки делается ложный вывод.

Однако операция логического следования несколько отличается от обычного понимания слова «следует». Если первое высказывание (предпосылка) ложно, то вне зависимости от истинности или ложности второго высказывания (вывода) составное высказывание истинно. Это можно понимать таким образом, что из неверной предпосылки может следо­вать что угодно.

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

Докажем методом сравнения таблиц истинности (табл. 3.8 и 3.9), что операция импликации А -> В равносильна логическому выражению А vВ.

Таблица 3.9. Таблица истинности логического выражения АvВ

A	B	!A	!Аv В
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

Таблицы истинности совпадают, что и требовалось доказать.

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

Логическая операция эквивалентности «А тогда и только тогда, когда В» обозначается А~В и выражается с помощью логической функции .F10, которая задается соответствующей таблицей истинности (табл. 3.10).

Таблица 3.10. Таблица истинности логической функции эквивалентности

A	B	F10
0	0	1
0	1	0
1	0	0
1	1	1

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

Рассмотрим, например, два высказывания: А = «Компьютер может производить вычисления» и В = «Компьютер включен». Составное высказывание, полученное с помощью операции эквивалентности, истинно, когда оба высказывания либо истинны, либо ложны:

«Компьютер может производить вычисления тогда и только тогда, когда компьютер включен».

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер не включен».

Составное высказывание, полученное с помощью операции эквивалентности, ложно, когда одно высказывание истинно, а другое — ложно:

«Компьютер может производить вычисления тогда и только тогда, когда компьютер не включен».

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включен».