Лекции по математической логике и теории алгоритмов (стр. 6 из 10)

Найдем коэффициенты с_к. Для этого последовательно придадим переменным x₁,x₂,…,x_n значения из каждой строки таблицы истинности. В итоге получим систему из 2ⁿ уравнений с 2ⁿ неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(x₁,x₂,…,xn).

2.

Метод, основанный на преобразовании формул над множеством связок {ÿ,&}. Строят некоторую формулу Ф над множеством связок{Ÿ,&}, реализующую данную функцию f(x₁,x₂,…,x_n). Затем заменяют всюду подформулы вида A на A∆1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример 3.1.1. Построить полином Жегалкина функции f(x,y)=xØy.

Решение.1. (метод неопределенных коэффициентов). Запишем искомый полином в виде

P(x,y)= c₀∆с₁x∆c₂y∆c₁₂xy Пользуясь таблицей истинности

x	0	0	1	1
y	0	1	0	1
xØy	1	1	0	1

получаем, что f(0,0)=P(0,0)= c₀=1, f(0,1)=P(0,1)= c₀∆ c₂=1, f(1,0)=P(1,0)= c₀∆ c₁=0, f(1,1)=P(1,1)= c₀∆с₁∆c₂∆c₁₂=1

Откуда последовательно находим, c₀=1, с₁=1, c₂=0, c₁₂=1. Следовательно xØy=1∆x∆xy (сравните с утверждением 3.1).

2.(Метод преобразования формул.) Имеем

x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .

Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.

Глава IV. Высказывания. Предикаты.

§4.1. Высказывания.

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

Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно (значение И или 1) или ложно (значение Л или 0) в конкретный момент времени. Например, «5-простое число», «нажата клавиша «Esc»» и т.д. При помощи связок «не», «и», «или», «если,… то», «если и только если» (им отвечают операции «Ÿ», «&», «¤», «Ø», «~» соответственно) можно построить более сложные высказывания (предложения). Так строится алгебра высказываний.

Для упрощения записи сложных высказываний вводится старшинство связок: «Ÿ», «&», «¤», «Ø», «~», что помогает опустить лишние скобки.

Простые высказывания назовем пропозициональными переменными.

Введем понятие формулы.

1. Пропозициональные переменные являются формулами.

2. Если А, В формулы, то выражения ŸА, А⁄В, А¤В, АØВ, А~В являются формулами.

3. Формулами являются только выражения построенные в соответствии с пп.1 и 2.

Формула, принимающая значение И при всех значениях пропозициональных переменных называется тавтологией (или общезначимой), а формула, принимающая значение Л при всех значениях пропозициональных переменных называется противоречием (или невыполнимой)

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

§4.2. Предикаты. Логические операции над предикатами.

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

Определение 2.1 Пусть x₁,x₂,…,xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x₁,x₂,…,x_n) принадлежат множеству M=(M1,M2,…Mn), которое будем называть предметной областью (т.е. x_iœM_i, где Мi называются областью определения переменной хi). Предикатом местности n (n-местным предикатом), определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л.

Пример 4.2.1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2.» — двуместный предикат, определенный на множестве пар натуральных чисел M=NäN. Очевидно, D(4,2) = И, D(3,5) = 0.

Пример 4.2.2. Q(x) ==«x²<-1, хœR» — одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(1) = Л, Q(5) = Л, и вообще предикат Q(x) — тождественно ложен, т. е.

Q(x) = Л для всех хœR.

Пример 4.2.3. В(x,у,z) =«х²+y²<z; х,у,zœR.» — трехместныйпредикат,определенный на R³. В(1,1,-2)=Л, В(1,1,2)=И.

Предикат Р, определенный на M, называется тождественно истинным, если он принимает значение И при любых значениях предметных переменных; Предикат Р называется тождественно ложным, если он принимает значение Л при любых значениях предметных переменных. Предикат Q из примера 4.2.2. является тождественно ложным.

Поскольку предикаты — это функции со значениями во множестве высказыраний, где введены логические операции, то эти операции естественно определяются и для предикатов. Пусть P и Q — предикаты, определенные наM. Тогда

1. ¬P(x , x ,…, x_n ) = P(x , x ,…, x )

^∧ 1 2 n 1 2 n ^∧ 1 2 n

3. (P ∨ Q)(x₁,x₂,…,x_n) = P(x₁,x₂,…,x_n) ∨ Q(x₁,x₂,…,x_n)

4. (P → Q)(x₁,x₂,…,x_n) = P(x₁,x₂,…,x_n) → Q(x₁,x₂,…,x_n) Предикаты Р и Q, определенные на M, называются равносильными (пишут Р=Q), если P(x₁,x₂,…,xn)=Q(x₁,x₂,…,xn)для любого набора (x₁,x₂,…,x_n) предметных переменных изM.

Теорема 4.2.1 Множество n-местных предикатов, определенных на M, образует булеву алгебру предикатов. Т.о., для них справедливы основные эквивалентности (см. §1.6).

§4.3. Кванторы, их свойства.

Пусть P(x₁,x₂,…,xn) — n-местный предикат, определенный на M. Зафиксируем x_i=a. Определим (n-1)-местный предикат Q(x₁,x₂,…,xk-1, xk+1,xn) следующим образом: Q(x₁,x₂,…,xk-1,xk+1,xn)=P(x₁,x₂,…,xk1,a,xk+1,xn). Говорят, что предикат Q(x₁,x₂,…,xk-1, xk+1,xn) получен из предиката P(x₁,x₂,…,xn) фиксацией значения i-й переменной: x_i=a.

Определение4.3.1. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое "xP(x) (читается «для любого х Р(х)»}, которое истинно тогда и только тогда, когда Р(х) — тождественно истинный предикат. О высказывании "xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.

Определение 4.3.2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое $xP(x) (читается «существует х Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании $xP(x) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х.

Замечание 1. Обозначения " и $ для кванторов — это перевернутые латинские буквы А и Е соответственно, которые являются первыми буквами в английских словах All — все, Exist — существовать.

Замечание 2. Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами (или предикатами любой местности).

Пусть P(x₁,x₂,…,xn) — n-местный предикат, определенный на M. Зафиксируем в нем значения переменных x₁,x₂,…,x_k-1,x_k+1,x_n. На полученный одноместный предикат Q(x_к) навесим квантор всеобщности (существования), получим высказывание. Тем самым фиксированному набору значений переменных x₁,x₂,…,x_k-1,x_k+1,x_n с помощью квантора всеобщности (существования) поставлено в соответствие высказывание. Говорят, что этот (n-1)-местный предикат переменных x₁,x₂,…,x_k-1,x_k+1,x_n получен из исходного предиката P(x₁,x₂,…,x_n) навешиванием квантора всеобщности (существования) по k-й переменной. Этот предикат обозначают: "x_кP(x₁,x₂,…,x_n) ($x_к P(x₁,x₂,…,x_n)). Об к-й переменной (которой уже нет) говорят, что она связана квантором всеобщности (существования).

Пример 4.3.1. Пусть D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2.» — двухместный предикат.

Навесим последовательно на его переменные кванторы. Ясно, что

1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1

4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2)=0 8) "x1$x2D(x1,x2)=1.

Таким образом (сравнением 7 и 8 в последнем примере) мы доказали теорему:

Обычно, связки и кванторы упорядочиваются по приоритету следующим образом Ÿ, ", $, &, ¤, Ø, ~.

Теорема 4.3.1. Разноименные кванторы, вообще говоря, не коммутируют.

Теорема 4.3.2. (основные равносильности, содержащие кванторы) Имеют место следующие равносильности:

1. Законы де Моргана

∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x)