Логические функции и элементы

1.2 Логические функции и элементы

1.2.1 Основы алгебры логики

Теоретической основой цифровых устройств является алгебра логики – раздел математической логики¹.

В качестве переменных (аргументов) в алгебре логики используются простые высказывания ². Например, «Дует ветер», «Качаются деревья».

О каждом из них можно утверждать, истинно оно или ложно.

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

Например, «Не дует ветер, однако качаются деревья», «Дует ветер, и качаются деревья ³». Последнее высказывание эквивалентно: «Деревья качаются тогда и только тогда, когда дует ветер». Следовательно, логические связки могут формулироваться различно.

В алгебре логики допускаются любые грамматически правильные высказывания, и игнорируется смысловая нагрузка. Например, высказывание: «Если качаются деревья, то дует ветер⁴» - допустимо.

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

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

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

Ответ: если Вы не закончили чтение книги или не сходили ни в театр, ни в кино, и, хотя была хорошая погода, не были на пляже.

Логические функции (далее функции), их аргументы принимают два значения: 1 (истина) или 0 (ложь) и обозначаются буквами (например, F₀, F₁, F₂,…,F_n; X₀, X₁, X₂,..., X_n, A, B,..., Z).

Разные комбинации значений переменных в функциях (0 и 1) называются наборами. Функция является полностью заданной, если указаны ее значения для всех наборов значений переменных. Сопоставляя каждому набору значение функции (0 или 1), можно получить табличное задание функции – таблицу истинности. Таким образом, функции алгебры логики конечны.

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

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

 

 

¹ Математическая логика – часть формальной логики.

² Другое название, встречающиеся в литературе: алгебра высказываний.

³ Здесь логическую связку можно осуществить бессоюзным образом не потеряв смысл логического высказывания.

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

⁵ Другие названия: Аристотелева, бинарная.

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

Пример логических заключений.

Все люди смертны. Сократ человек. Сократ смертен (Сократ).

Из первой посылки: все люди смертны (истина) и второй посылки: Сократ человек (истина), делается заключение: Сократ смертен (истина).

Пример:

Расследовать происшествие:

Кота по имени Тунец убил либо Джек, либо Любопытство. Действительно ли этого кота убило Любопытство?

Известно, что:

- каждого, кто любит животных, кто-то любит;

- любого, кто убивает животных, никто не любит;

- Джек любит животных.

Предположим, что кота Тунца убило не Любопытство. Мы знаем, что это сделал либо Джек, либо Любопытство; в таком случае это должен был сделать Джек.

Итак, Тунец – кот, а коты – животные, поэтому Тунец – животное. Любого, кто убивает животное, никто не любит, поэтому вывод – никто не любит Джека. С другой стороны, Джек любит животных, поэтому кто-то его любит; таким образом, возникает противоречие. Это означает, что кота убило Любопытство.