Методические рекомендации по изучению дисциплины (стр. 4 )

S(В)=1: ;

S(В)=2: ;

S(В)=3: ;

S(В)=4: ;

S(В)=5: .

Согласно определения 2.2.2 (пункт а), значения подформул сложности 0, т. е. переменных А1; А2; А3 полагаем равными и, л, и соответственно. Затем, используя таблицу истинности (смотри пункт б) определения 2.2.2), вычисляем значения подформул сложности 1, 2 и т. д. пока не дойдем до значения А(и,л,и) самой формулы А(А1;А2;А3).

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

S(В)=0: и; л; и ;

S(В)=1: л; л;

S(В)=2: л; и;

S(В)=3: л; и;

S(В)=4: и;

S(В)=5: и,

т. е. А(и,л,и)=и.

Таблицы истинности

Пример показывает, что вычисление значения формулы А(А1;А2;А3) на наборе аналогично вычислению значения выражения обычной алгебры при заданных значениях входящих в него букв. Так как значениями букв являются (в общем случае) действительные числа, то множество всех наборов значений для букв, входящих в данное выражение, бесконечно и вычислить его значение на всех этих наборах не представляется возможным.

В алгебре высказываний аналогичная задача решается положительно.

Предложение Число всех различных наборов значений истинности длины п равно 2п.

Доказательство: а) Базис индукции (п=1). Наборами значений истинности длины 1 являются наборы ; , т. е. их число равно двум. Вычисление по формуле также дает 21=2.

б) Индукционное предположение (п=к). Пусть число всех различных наборов значений истинности длины к равно 2к.

в) Индукционный шаг (п=к+1). Покажем, что число всех наборов значений истинности длины к+1 равно 2к+1.

Все наборы длины (к+1) разобьем на два класса. В первый из них включим те наборы, последняя координата которых – «л», т. е. все наборы вида:

; .

Во второй класс включим все наборы, последняя координата которых – «и» , т. е. все наборы вида:

; .

Очевидно, что любой набор значений истинности длины (к+1) попадет или только в первый класс или только во второй класс. Если от каждого набора, попавшего в первый класс, отбросить последнюю координату, то получим все наборы значений истинности длины к. По индукционному предположению их число равно 2к. Так как удаление последней координаты у каждого набора из первого класса не меняет их числа, то число наборов попавших в первый класс, также равно 2к. Аналогичным образом, число всех наборов второго класса равно 2к. Следовательно, число всех различных наборов длины (к+1) равно: 2к+2к=2к+1. ÿ

Конечность числа наборов значений истинности длины п позволяет построить для формулы А(А1;А2;…;Ап)ÎL(A) таблицу, аналогичную таблице 2.1.2.

Эта таблица имеет вид 2.3.1 и называется таблицей истинности для формулы А(А1;А2;…;Ап).

В таблице 2.3.1 последний столбец представляет собой столбец значений формулы А(А1;А2;…;Ап), т. е. . В частности . Для упрощения вычислений перед столбцом значений для самой формулы А в таблице предусматриваются еще и столбцы для вычисления значений некоторых подформул этой формулы.

Таблица 2.3.1

Пример Ниже приводится таблица истинности для формулы А = А(А1;А2;А3) из примера 2.2.2 (смотри таблицу 2.3.2).

Упражнение Построить таблицы истинности для следующих формул:

а) ;

б) .

Обратной по отношению к решенной задаче о вычислении истинностного значения формулы на заданном наборе значений истинности является задача о нахождении всех таких наборов значений истинности для переменных А1;А2;…;Ап, на которых формула А=А(А1;А2;…;Ап) принимает фиксированное значение . В определенном смысле, эта задача является аналогом задачи решения алгебраических уравнений в обычной алгебре. Конечно, в алгебре высказываний она может быть решена, описанным выше, методом построения таблиц истинности с последующим выбором из нее тех наборов значений истинности, на которых формула А принимает заданное значение τ. Но можно найти все эти наборы, решая логические уравнения (и их системы) непосредственно.

А1	А2	А3				А
л	л	л	и	и	л	и
л	и	л	и	и	л	и
и	л	л	и	л	л	л
и	и	л	л	и	и	и
л	л	и	и	и	и	и
л	и	и	и	и	и	и
и	л	и	и	л	и	и
и	и	и	и	л	и	и

Таблица 2.3.2

Пример Найдем все наборы значений истинности, на которых формула А(А1;А2;А3) из примера принимает значение л, решая уравнение

. (1)

Исходя из определения операции Ú, получаем, что это уравнение равносильно такой системе:

(2)

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

(3)

Если же мы взялись бы решать второе уравнение системы (2), то для нахождения всех его решений нам бы пришлось решить систему:

(4)

которая сложнее, чем система (3).

Решения системы (3) выписываем непосредственно, исходя из определения операций & и ¯:

(5)

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

Отметим, что этот путь также позволяет построить таблицу истинности формулы А(А1;А2;А3), так как, исходя из полученного результата мы заключаем, что на всех остальных наборах формула А(А1;А2;А3) является истинной.

Во многих случаях второй путь построения таблицы истинности для формулы А(А1;А2;…;Ап) более экономичен.

Упражнение Найти все наборы значений истинности, на которых формула:

а) принимает значение «и»;

б) принимает значение «л».

Классификация формул алгебры высказываний

Определение Формула А(А1;А2;…;Ап) называется:

а) выполнимой, если существует хотя бы один набор значений истинности для переменных А1;А2;…;Ап такой, что

;

б) тождественно истинной (или тавтологией), если

для любого набора значений истинности для переменных А1;А2;…;Ап;

в) тождественно ложной (или противоречием), если

для любого набора значений истинности для переменных А1;А2;…;Ап.

Из определения 2.4.1 непосредственно вытекает, что всякая тождественно истинная формула является выполнимой (но не наоборот); а также, что отрицание тождественно истинной формулы является тождественно ложной формулой и, что отрицание выполнимой, но не тождественно истинной формулы, также является выполнимой формулой.

Отметим, что метод построения таблиц истинности позволяет по любой формуле А=А(А1;А2;…;Ап) определить к какому из этих трех классов относится формула А.

Заметим также, что решение логических уравнений и систем, основанное на определении операций &, Ú, ®, «, Ø, зачастую позволяет получить ответ значительно быстрее. Допустим, что нам необходимо выяснить, является ли формула А(А1;А2;…;Ап) выполнимой. Для этого нужно найти хотя бы одно решение уравнения А(А1;А2;…;Ап)=и. Если далее нужно выяснить, является ли эта формула тавтологией, то нужно убедиться, что уравнение А(А1;А2;…;Ап)=л решений не имеет.

Пример Проиллюстрируем сказанное на примере формулы

(1)

Решая уравнение А(А,В,С)=и, сводим его к системе

(2)

Второе уравнение системы (2) равносильно совокупности трех систем:

; ; (3)

Решениями первой из этих систем являются наборы и . Подставляя первый набор в первое уравнение системы (2) вместо переменных А и В соответственно, получаем, что С=и; т. е. А(л;л;и)=и и выполнимость формулы (1), тем самым, установлена. Понятно, что если бы подстановка первого набора привела бы к уравнению, не имеющему относительно С решений, то нужно было бы подставить второй набор . Если и здесь мы не получили бы необходимого результата, то нужно было бы переходить ко второй системе совокупности (3) и, при необходимости, к третьей.

Решая уравнение А(А;В;С)=л получаем, что оно равносильно следующей совокупности трех систем:

(4)

(5)

(6)

Нетрудно видеть, что единственным решением второго уравнения системы (4) является набор . Подставив его в первое уравнение этой системы, получаем уравнение относительно С:

,

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

Упражнение Выяснить являются ли данные формулы выполнимыми, тождественно истинными или тождественно ложными:

а) ;

б) ;

в) .

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

(7)

Если мы, рассуждая по этой схеме, в качестве А, В и С возьмем такие высказывания, что посылки (А®В) и (В®С) окажутся истинными, то и заключение (А®С) также будет истинным. Некоторые наиболее применимые в рассуждениях тавтологии получили специальные названия. Ниже приводятся примеры таких тавтологий:

1 - закон двойного отрицания;

2 - закон исключения третьего;

3 - правило силлогизма;

4 - правило контрапозиции;

5 - правило объединения посылок;

6 - правило разъединения посылок;

7 - правило перестановки посылок;

8 - правило приведения к абсурду.

Упражнение Доказать, что вышеприведенные формулы 1-8 являются тавтологиями.

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

1 Пусть А – формула содержащая переменную А (далее эту формулу будем обозначать через А(А), не выделяя остальные переменные этой формулы) и В – любая формула. Через обозначим формулу, которая получается из А(А) посредством замены каждого вхождения в эту формулу переменной А на формулу В.

Пример Пусть и , тогда

(7)

Будем говорить, что формула (7) получена из формул А(А) и В посредством применения к ним оператора подстановки .