Множества. Комбинаторика. Отношения (стр. 7 )

Пусть Ф = {f1(m), f2(m), …} – множество функциональных символов, где верхние символы указывают местность (арность) символов. Если арности из контекста известны, то верхние индексы будем опускать.

Формулы над множеством Ф – это выражения вида и только они:

1)  fк, где к – нульместный символ; fj(xi1,…,xin), где fj – n-местный функциональный символ, xi1,…,xin – переменные из множества Х.

2)  fm (A1,A2,…,As), где fm – s-местный функциональный символ, Ai – либо формула над Ф, либо переменная из Х, 1 £ i £ s.

Пусть Ф – множество функциональных символов, Р – множество соответствующих им функций. Суперпозицией над множеством Р называется всякая функция F, которую можно реализовать формулой над множеством Ф.

Формула алгебры логики называется выполнимой, если существует набор значений переменных, на которых реализуемая ею функция принимает значение 1, и опровержимой, если 0. Формула называется тождественно истинной или тавтологией, если она реализует функцию “тождественная единица”, и тождественно ложной, если 0. Проблема разрешимости заключается в задаче: указать алгоритм, позволяющий для каждой формулы выяснять, является ли она тождественно истинной. Ответ на этот вопрос можно дать после изучения нормальных форм.

Упражнения

Являются ли формулы тождественно истинными:

1)  ((xÅy)Ûz)(xÞyz);

2)  (xÚØy)zÞ((xÛz)Åy)½(x(yz));

3)  (XÞY) Þ ((XÚZ) ÞYÚZ).

Решение 1):

Формула является тождественно истинной, если она принимает на всех наборах значение 1. Построим таблицу истинности данной формулы.

X	Y	Z	XÅY	(XÅY)ÛZ	YZ	XÞYZ	F
0	0	0	0	1	0	1	1
0	0	1	0	0	0	1	0
0	1	0	1	0	0	1	0
0	1	1	1	1	1	1	1
1	0	0	1	0	0	0	0
1	0	1	1	1	0	0	0
1	1	0	0	1	0	0	0
1	1	1	0	0	1	1	0

Таблица истинности данной формулы (10010000), т. е. данная формула не является тождественно истинной.

Упражнения

Задание: Построить таблицы истинности данных формул

1) F(x, y, z) =. (Ответ: формула тождественно истинна).

2) F(x, y, z) =. (Ответ: (11111010)).

3) F(x, y, z) =. (Ответ: (00001011)).

4) F(x, y, z) =. Ответ: (10100011)

5) F(x, y, z) =. Ответ: (00000110)

2.1.4. Алгебра Буля

Непустое множество U с тремя операциями +,*,’ (сложение, умножение, дополнение) называется алгеброй Буля, если выполняются следующие условия:

1)  a+b = b+a, ab = ba, "a, b Î U;

2)  , "a, b Î U;

3)  , (дистрибутивность сложения относительно умножения и умножения относительно сложения);

4)  т. е. все элементы являются идемпотентами по отношения к обеим операциям;

5)  законы двойственности де Моргана.

Нейтральный элемент 1 операции умножения называется универсальным элементом алгебры Буля.

Примеры.

1)  P(A), где + = È, * = Ç, ‘ = дополнение, 0 = Æ, 1 = А.

2)  Алгебра высказываний, + = Ú, * = &, ‘ – отрицание.

3)  Контакты электрических сетей, если трактовать + как параллельное соединение контактов, * последовательное соединение контактов, 1 – есть ток в цепи, 0 – нет тока в цепи, – размыкание контакта x.

4)  {0;1}, a+b = max {a, b}, a*b = min {a, b}.

5)  Множество делителей числа n, если a+b =НОК(a, b), a*b = НОД(a, b), .

6)  Сегмент [x, y], где a+b = max {a, b}, a*b = min {a, b}, 0 =x, 1 = y, a’ – точка, симметрическая с точкой а относительно середины сегмента.

2.1.5. Эквивалентные формулы

Формулы алгебры логики А и В называются эквивалентными, если на всяком наборе значений переменных (входящих хотя бы в одну из формул А и В) значения функций jА и jВ совпадают, т. е. если jА = jВ. Приведем основные эквивалентности.

1)  (законы коммутативности)

2)  (законы ассоциативности)

3)  (законы дистрибутивности)

4)  (законы двойственности де Моргана)

5)  (правила склеивания)

6)  (правила поглощения)

7)  (правило обобщенного склеивания)

8)  x&x = x, xÚx = x (законы идемпотентности)

9)  x&0 = 0, xÚ0 = x, x&1 = x, xÚ1 = 1, (xÞ0) = (свойства относительно констант)

10)  (закон исключенного третьего)

11)  x&= 0(закон противоречия)

12) 

13)  (закон двойного отрицания)

14)  =1

15)  (замена импликации)

16)  (замена эквиваленции)

17)  (х Å у) = `х у Ú х`у

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

X	y
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

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

Эквивалентные формулы используются при упрощении формул. Например, упростим А1(x1,x2,x3) = . По правилу склеивания. К дизъюнкции применим тождественное преобразование , получим . Аналогично, . Поэтому А1(x1,x2,x3) = .