МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

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

Опр. Алфавитом называется произвольное множество символов.

Введем алфавит, состоящий из следующих групп симво-

лов:

1.x, y, z, p, …А, В,… – пропозициональные переменные;

2.&, , , , – логические связки;

3.(, ) – 2 технических символа.

Опр. (формулы алгебры высказываний):

1.Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний. Формулы такого вида называются простейшими (атомами).

2.Если x – формула алгебры высказываний (АВ), то ( x) – формула (АВ).

3.Если x и y – формулы алгебры высказываний, то (x&y), (x y), (x y), (x y) – тоже формулы (АВ).

4.Никаких других формул (АВ), кроме получающихся со-

гласно п.п.1–3 нет.

Определения такого типа называются индуктивными. В них имеются прямые пункты (1,2,3), где задаются объекты, которые в дальнейшем именуются определяемым термином и косвенный пункт (4), в котором говорится, что такие объекты исчерпываются заданными в прямых пунктах. Среди прямых пунктов имеются базисные (1), где указываются некоторые конкретные объекты, именуемые в дальнейшем определяемым термином, и индуктивные пункты (2,3), где даются правила получения определяемых объектов из уже имеющихся объектов, в частности из объектов, перечисленных в базисных пунктах.

Замечание: «О силе связок».

Для упрощения записи формул (уменьшения числа скобок

вних) будем считать, что:

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

, ,

11

2)внешние скобки, заключающие внутри себя все остальные символы, составляющие формулу,

можно опускать.

Учитывая это соглашение, а также опустив знак конъюнкции, формулу x& y z x y z можно записать в ви-

де:

xy z x y z .

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

Понятие булевой функции. Таблица истинности формулы

Подставляя в формулу вместо пропозициональных переменных x, y, z,… значения 0,1, и выполняя действия, мы будем получать значения формулы.

Опр. Булевой функцией называется функция, заданная на множестве {0,1} и принимающая значения из этого же множества.

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

Лемма. Существует 2n наборов, элементами которых являются нули и единицы, длины n. (Длина набора – число символов, входящих в набор).

Доказательство методом математической индукции:

1.Пусть n=1: Имеем 2 набора {0},{1}.

2.Предположим, что утверждение леммы справедливо для n = k. Существует 2k наборов длины k, элементами которых являются нули и единицы.

12

Применим к набору (1) следующее преобразование: сначала допишем в конце набора 0, а затем 1. В результате, из одного набора длины k получим два набора длины (k+1).

Таким же образом поступим с каждым из 2k наборов.

Всего наборов получится: 2 2k =2k 1. По принципу математической индукции утверждение леммы справедливо для любого натурального числа n.

Теорема. Существует 22n булевых функций от n переменных.

Рассмотрим булевы функции от 2 переменных:

x y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15

Среди перечисленных 16-ти функций две функции – константы, 4 функции зависят от одной переменной и 10 – от 2-х.

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

13

Опр. Формула (АВ) называется тождественно истинной (тавтологией), если она принимает значение «истина» при любых значениях переменных, входящих в формулу.

Пример: F(x,y)=(x y) (y x)

Равносильные формулы

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

Обозн. F1 F2

Читается: формула F1 равносильна формуле F2.

Например: F1= x x& y ; F2= x y

x x& y x y

Свойства логических операций

(Основные равносильности (АВ))

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

1. x x…………..закон двойного отрицания

14

2.x&x x………..идемпотентность конъюнкции

3.x x x………...идемпотентность дизъюнкции

4.x&y y&x…….коммутативность конъюнкции

5.x y y x……...коммутативность дизъюнкции

6.(x&y)&z x&(y&z) …..ассоциативность конъюнкции

7.(x y) z x (y z) ……ассоциативность дизъюнкции

8.x&(y z) (x&y) (x&z) ...дистрибутивность конъюнкции относительно дизъюнкции

9.x (y&z) (x y)&(x z) …дистрибутивность дизъюнкции относительно конъюнкции

10.x&(y x) x……………..закон поглощения

11.x (y&x) x……………...закон поглощения

12.x& y x y …………….закон де Моргана

13.x y x& y………….....закон де Моргана

14.x y y x

15.x y (x y)&(y x)

16.x y x& y

17.x y x y

18.x&y x y

19.x y x y

21.x x 1…………………закон исключенного третьего

22.x&1 x

23.x 1 1

24.x&0 0

25.x 0 x.

Докажем формулу (12): x& y x y

15

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

Например.

1.x x& y (9) x x & x y (21) 1&(x y) (22) x y.

2.x& x y (8) x&x x& y (20) 0 (x&y) (25) x&y.

Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ)

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

Опр. Формула F называется элементарной конъюнкцией

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

Примеры:

Опр. ДНФ (КНФ) называется формула, являющаяся дизъюнкцией (конъюнкцией) элементарных конъюнкций (дизъюнкций).

Примеры: const. 0 –– ДНФ, x y – ДНФ,

x y y z x – ДНФ.

Теорема. Всякая, не тождественно ложная формула (АВ) равносильна некоторой ДНФ.

Рассмотрим 2 способа нахождения ДНФ: 1) табличный;

16

2) аналитический (с помощью равносильностей). Пример. 1) Табличный:

F= x y z y . Составим таблицу истинности:

выделить те строчки таблицы, в которых значение формулы равно 1;

напротив каждой выделенной строки записать конъюнкцию переменных, входящих в формулу;

поставить знак отрицания над теми переменными, значения которых на данном наборе равны 0;

составить дизъюнкцию полученных элементарных конъ-

упростить полученную ДНФ с помощью основных равносильностей до минимальной ДНФ.

ДНФ: x y z x y z x y z x y z x y z

x y ( z z ) x y z x y ( z z )

x y x y x y z

( x x) y x y z

y x y z

y x z – минимальная ДНФ.

Аналитический:

 избавиться от импликаций с помощью равносильностей;

17

используя законы де Моргана отрицания внести внутрь формулы так, чтобы они относились к переменным, двойные отрицания удалить;

с помощью дистрибутивного закона получить ДНФ;

упростить ДНФ. Пример.

x y z x y z

x y z x y z x y z x y z xzx yzx y z

xyz y z xyz y z y z – минимальная ДНФ.

Совершенная ДНФ

Опр. ДНФ называется совершенной относительно данного множества переменных, если каждая переменная входит в каждую элементарную конъюнкцию (с отрицанием или без отрицания), причем ровно один раз.

Элементарные конъюнкции, входящие в СДНФ должны быть попарно различными.

Например: 1) xyz x yz – СДНФ от x, y, z.

2) xy – СДНФ от x, y, но не является СДНФ от

x, y, z.

Замечания 1. const. 0 – СДНФ;

2. ДНФ, найденная табличным способом, яв-

ляется СДНФ.

3. F= x – СДНФ от переменной x, но не являет-

ся СДНФ от x, y, z, которая может быть из нее получена:

F= x = x y y z z = x y z x y z x y z x y z – СДНФ от x, y, z.

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

КНФ, СКНФ – самостоятельно.

18

Понятие о полноте системы булевых функций

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

Основные логические связки, используемые нами – &, ,, . С помощью равносильности x y x y мы можем во всех формулах, в которых встречается подформула x y заменить ее на x y и, тем самым, исключить из использования знак .

Т1 Система булевых функций {&, , } является полной. Любую булеву функцию можно записать в СДНФ. (на-

пример табличным способом).

Т2 Система булевых функций { , } является полной. Следует из Т1 и законов де Моргана: x& y x y

x& y x y x& y x y .

Т3 Система булевых функций {&, } является полной. x y x& y .

Т4 Система булевых функций { , } является полной. Следует из Т2 и равносильности x y x y .

Т5 Система булевых функций {&, , }, не содержащая, не является полной.

Доказательство: Рассмотрим булеву функцию специального вида. Назовем функцию (или формулу (АВ)) f(x1,x2,…,xn) сохраняющей истину, если f(1, 1,…,1)=1.

Докажем, что булевы функции &, , сохраняют истину. Пусть f1(x1,x2,…,xn) и f2(x1,x2,…,xn) – функции, сохраняющие ис-

тину, т.е. f1(1, 1,…,1)=1 и f2(1, 1,…,1)=1. Тогда: f1 & f2=1;

f1 f2=1; f1 f2=1.

19

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

Но среди булевых функций есть функции, не сохраняющие истину.

Например: f x,y x y . f 1,1 1 0 0 .

Эту функцию нельзя получить с помощью рассматриваемой системы булевых функций {&, , }.

Следствие: Системы булевых функций {&, }, {&, }, { , }, {&}, { }, { } неполны. (Как подсистемы неполных систем).

Т6 Система булевых функций { } неполна.

Пусть даны пропозициональные переменные x1, x2, …,.xn. При помощи отрицания можно получить только x1, x2, …,.xn, x1 , x2 , ,.xn , т.е. функции от одной переменной и ни одной функции с двумя переменными. Это доказывает неполноту этой системы.

Вместе с тем существуют полные системы, содержащие одну булеву функцию, которая выражается через &, , .

Штрих Шеффера

Обозн. x y (читается «x штрих y). Задается таблицей истинности:

20