Логические формулы

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

A ® В Ú С;

(A « Ú ) ® Ù ;

B ® Ú (С Ù B) «(A Ú B) Ù ® С и т.д.

Такие высказывания называются логическими формулами или булевыми функциями, а входящие в них простые высказывания – логическими переменными. Символы Ø, Ù, Ú, ®, «называют логическими связками.

Формулы логики высказываний можно рассматривать двояко.

Принимая А, В, С за обозначение простых высказываний, логическая формула будет представляться как определенное сложное высказывание. Например, если обозначить А – «Будет дождь», В – «Я возьму зонт», С – «Я надену плащ», то A®В Ú С – запись сложного высказывания «Если будет дождь, то я возьму зонт или надену плащ».

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

Для правильного вычисления значения логических формул необходимо задать порядок выполнения логических операций. Сначала выполняется операция отрицания Ø, затем конъюнкция Ù и дизъюнкция Ú (они равноправны), затем импликация ® и, последней, эквивалентность «. Как и в алгебре, скобки необходимы для изменения порядка действий, а равноправные операции вычисляются слева направо.

Таким образом, для вычисления значения выражения (A « Ú ) ® Ù необходимо сначала определить и , затем выполнить дизъюнкцию Ú , после этого подсчитать значение выражения, стоящего в скобках: A « Ú , далее выполнить конъюнкцию высказываний Ù и, наконец, соединить вычисленные значения высказываний A « Ú и Ù с помощью импликации: (A « Ú ) ® Ù . Порядок выполнения операций будет таков:

.

Пусть простые высказывания А и В истинны: А =1, В =1. Тогда и являются ложными высказываниями: =0, =0. Также ложной будет и дизъюнкция Ú =0. Значение высказывания в скобках A « Ú =0, так как эквивалентность истина«ложь дает ложь. Конъюнкция ложных высказываний Ù также ложна: Ù =0. Результирующее высказывание представляет собой соединение ложь®ложь, что по определению операции импликация есть истина. Значит, (A « Ú ) ® Ù =1 при А =1 и В =1.

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

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

Построим таблицу истинности для приведенного выше сложного высказывания:

(A « Ú ) ® Ù .

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

А =1, В =1;

А =1, В =0;

А =0, В =1;

А =0, В =0.

Вычислим значение сложного высказывания в каждом случае по действиям.

А	В			Ú	A« Ú	Ù	(A « Ú ) ® Ù

Двойной чертой отделяем значения исходных переменных от вычисляемых значений по определениям логических операций.

Дата добавления: 2015-08-20