Элементы математической логики

Логическое сложение. (disjunctio – лат. различаю) Перед тем как привести определение этой операции, дадим некоторые разъяснения. Союз «или» в обиходе мы применяем в двух значениях: исключающем и неисключающем. Разъясним это примерами.

1. Рассмотрим повествовательное  предложение: «Володя вчера в  шесть часов вечера читал книгу  или ехал в автобусе на стадион.»  Союз «или» использован в этом  предложении в неисключающем смысле — Володя мог читать и одновременное ехать в автобусе. Одно не исключает другого.

2. Рассмотрим еще одно  повествовательное предложение. «Володя  вчера наблюдал за ходом матча  с западной или восточной трибуны.»  Здесь союз «или» имеет исключающий  характер — две описываемые  ситуации исключают друг друга: нельзя наблюдать один и тот  же матч одновременно с двух  противоположных трибун.

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

Указание о необходимости выполнить логическое сложение высказываний A и B записывается так:

Таблица 5

Логическое сложение высказываний A и B

A	B	A+B
Шесть число кратное 3	19>37	Шесть число кратное 3 или 19>37

 

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

Это определение можно обобщить для любого количества логических0, С=0.

Таблица истинности дизъюнкции имеет следующий вид:

Таблица 6

Таблица истинности дизъюнкции

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1

 

Следующие логические законы можно назвать свойствами дизъюнкции: 11

1. Закон противоречия.
2. Закон равносильности (идемпотентности idem – лат. тот же самый; potens – лат. сильный) А+А=А
3. Закон исключения констант А+1=1, А+0=А

Логическое отрицание. (inversio – лат. переворачиваю) Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией. Обозначается A или A¬.

Иногда вместо приведенного определения используют другое, ему эквивалентное: присоединение слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания. В результате выполнения операции логического отрицания получается новое высказывание.

Таблица 7

Логическое отрицание

А
Число 5 является делителем числа 30	Число 5 не является делителем числа 30

 

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

Таблица 8

Таблица истинности инверсии

А
0	1
1	0

 

Закон двойного отрицания

Импликация. (implicatio - лат. тесно связываю) или логическое следование соответствует обороту «если…, то…», обозначается

Рис. 1.1.   – Импликация

A={Поезд прибывает на данный путь.}

B={Подается сигнал, что путь закрыт.}

Рассматриваемое сложное высказывание истинно, если:

1) поезд прибывает, сигнал  «закрыт» (1, 1, 1);

2) поезд не прибывает, сигнал «свободен» (0, 0, 1);

3) поезд не пребывает, сигнал «закрыт» (0, 0, 1) – если  поезд не пребывает, безопасен  любой сигнал;

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

Операция импликации в русском языке является самой «загадочной». Ей соответствую также следующие речевые обороты: «из А следует В»; «А имплицирует В»; «А достаточно для В»; «В необходимо для А».

Рис. 1.2.   – Операция импликации

Эквивалентность. (aequivalens – фр. равноценное) или равнозначность, соответствует оборотам речи «тогда и только тогда» и «в том и только в том случае», обозначается , или или

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

«Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку.»

В русском языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».

Рис. 1.3.   – Представление эквивалентности через конъюнкцию, дизъюнкцию и инверсию

Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначается

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

Представление эквивалентности через конъюнкцию, дизъюнкцию и инверсию =A*+*B.

 Сравнив таблицы истинности операций эквивалентности и сложения по модулю 2, можно сделать вывод, что эти сравнения являются инверсией друг друга, то есть A↔B=

Таблица 9

Таблица истинности инверсии

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

 

Рис. 1.4.   – Cвойства строгой дизъюнкции

Стрелка Пирса (символ Лукашевича) – логическая операция с двумя переменными, соответствует обороту речи «ни…ни», обозначается следующим образом F(A,B)=A↓B.

Выражение A↓B истинно в том и только том случае, когда оба высказывания А и В ложные.

A↓B =.

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

=A↓A

A*B=( A↓A)↓(B↓B)

A+B=( A↓B)↓(A↓B)

Cвойства Стрелки Пирса:

A↓A=

A↓=0

A↓0=

A↓1=0

Таблица 10

Таблица Стрелки Пирса

A	B	A↓A
0	0	1
0	1	0
1	0	0
1	1	0

 Штрих  Шеффера - – логическая операция с двумя переменными, соответствует обороту речи «не…не», обозначается следующим образом F(A,B)=A│B.

Выражение A│B ложно в том и только том случае, когда оба высказывания А и В истинны.

A│B =.

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

= A│B

A*B=( A│B)│(A│B)

A+B=( A│A)│(B│B) A│B)↓(A↓B)

Cвойства Стрелки Пирса:

A│A=

A│=1

A│0=

A│1=

Краткие выводы по первой главе

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Конъюнкция и дизъюнкция высказываний и высказывательных форм

 

2.1. Конъюнкция и дизъюнкция высказываний

 

Конъюнкцией высказываний А и В называется высказывание А∧В, которое истинно, когда оба высказывания истинны, и ложно, когда хотя бы одно из высказываний ложно. 12

Обозначают А∧В (читают: «А и В»).

Определение конъюнкции можно записать с помощью таблицы, называемой таблицей истинности.

А	В	А∧В
и	и	и
и	л	л
л	и	л
л	л	л

 

 

Рис. 2.1.   – Таблица истинности

Используя данное определение, находим значение истинности высказывания «число 28 делится на 7 и на 9», которое, как было установлено раньше, состоит из двух элементарных высказываний, соединенных союзом «и», т.е. является конъюнкцией. Так как первое высказывание истинно, а второе ложно, то, согласно определению конъюнкции, высказывание «число 28 делится на 7 и на 9» будет ложным.

Данной операции соответствует логическая связка И и символ  либо

Конъюнкцией высказываний  и  называют высказывание  (читается «а и бэ»), которое истинно в том и только том случае, когда истинны оба высказывания  и :

Рис. 2.2.   – Конъюнкция высказываний

Данная операция тоже встречается сплошь и рядом. Предположим, что Петя получает допуск к экзамену по высшей математике, если сдаёт курсовую работу и зачёт по теме. Рассмотрим следующие высказывания:

 – Петя сдал курсовую работу;

 – Петя сдал зачёт.

Заметьте, что в отличие от формулировки «Петя завтра сдаст» здесь уже в любой момент времени можно сказать, истина это или ложь.

Высказывание  (суть – Петя  допущен к экзамену) будет истинно в том и только том случае, если он сдал курсовик  и зачёт по . Если хоть что-то не сдано (см. три нижних строчки таблицы), то конъюнкция  – ложна.

Знак системы  соединяет входящие в неё уравнения/неравенства как раз по правилу И. Так, например, запись двух линейных уравнений  в систему  подразумевает то, что надо найти ТАКИЕ корни  (если они существуют), которые удовлетворяют и первому и второму уравнению.

Рассматриваемая логическая операция распространяется и на большее количество высказываний. Условно говоря, если в системе 5 уравнений, то её корни (в случае их существования) должны удовлетворять и 1-му и 2-му и 3-му и 4-му и 5-му уравнению данной системы.

Вновь обратим внимание на электротехнику: конъюнктивное правило хорошо моделирует выключатель в комнате и рубильник на электрическом щитке в подъезде (последовательное подключение). Рассмотрим высказывания:

 – выключатель в комнате включен;

 – рубильник в подъезде включен.

Конъюнкция читается самым что ни на есть естественным образом: 
 – выключатель в комнате включен и рубильник в подъезде включен.

Очевидно, что  тогда и только тогда, когда . В трёх других случаях (проанализируйте, каких) цепь разомкнётся и свет погаснет: .

Присоединим ещё одно высказывание: 
 – рубильник на подстанции включен.