Практическое занятие №12.Операции над предикатами и кванторами

Все логические операции логики высказываний справедливы и для предикатов (отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция). Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. В математической логике приписывание квантора к формуле называется связыванием, а переменную, к которой он относится, называют связанной иначе свободной. Например, в предикате "x A(x, y)Ú"z B(c, z) переменные x и z - связанные, а переменные у и z – свободные.

Чаще всего используют два вида кванторов:

 

Название	Прочтение	Обозначение
Квантор общности	«все», «всякий», «каждый», «любой»	"
Квантор существования	«существует», «найдется», «хотя бы один»	$

 

Пусть задан одноместный предикат P(x) на множестве Х = { a₁, a₂, a₃, a₄ }, тогда: "xP(x)=P(a₁)&P(a₂)&P(a₃)&P(a₄); $xP(x)=P(a₁)ÚP(a₂)ÚP(a₃)ÚP(a₄).

Говорят, что у квантора всеобщности конъюнктивная природа, а у квантора существования – дизъюнктивная. Квантор уменьшает число свободных переменных в логическом выражении и превращает трёхместный предикат в двухместный, двухместный — в одноместный, одноместный — в высказывание.

Примеры выполнения заданий

1. Пусть предикат Q(x,y) определен на конечных множествах:

X={a₁,a₂,a₃, a₄, a₅}, Y={b₁, b₂, b₃, b₄, b₅, b₆} и имеет таблицу истинности:

X	Y
b1	b2	b3	b4	b5	b6
a1	И	И	Л	Л	И	Л
a2	Л	Л	Л	И	И	Л
a3	И	И	Л	Л	И	И
a4	Л	И	Л	Л	И	И
a5	И	И	И	И	И	И

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

Решение. Результат применения кванторов общности и существования по x ÎX:

" xQ(x,y)	Y
b1	b2	b3	b4	b5	b6
Л	Л	Л	Л	И	Л
$ xQ(x,y)	И	И	И	И	И	И

 

Результат применения квантора общности по y ÎY: X "y Q(x,y) a1 Л a2 Л a3 Л a4 Л a5 И

Результат применения квантора существования по y ÎY: X $yQ(x,y) a1 И a2 И a3 И a4 И a5 И

 

Применив кванторы общности и существования повторно, получим восемь высказываний (0 -арных предикатов), представленных в таблице:

Высказывание	Значение истинности
" y " x Q(x, y)	Л
$ y " x Q(x,y)	И
" y $ x Q(x,y)	И
$ x " y Q(x,y)	И
" x $ y Q(x,y)	И
$ x $ y Q(x,y)	И

Задания для самостоятельного выполнения

1.Пусть предикат P(x, y) определен на множествах: X={a₁,a₂ a₃,a₄}, Y={b₁,b₂,b₃,b₄,b₅,b₆,b₇,b₈} и имеет таблицу истинности. С помощью кванторов постройте высказывания и определите их истинность:

0)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	И	Л	И	Л	И	И	Л
a2	Л	И	И	И	Л	И	И	Л
a3	И	И	Л	И	Л	Л	Л	Л
a4	И	И	Л	И	Л	Л	Л	Л

1)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	Л	Л	И	Л	И	И	Л
a2	Л	Л	Л	Л	Л	Л	Л	Л
a3	И	И	Л	И	Л	Л	Л	Л
a4	Л	Л	Л	И	И	Л	И	Л

2)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	Л	И	Л	И	Л	И	Л
a2	Л	И	И	Л	Л	Л	Л	И
a3	И	Л	Л	Л	Л	Л	Л	И
a4	Л	И	Л	И	И	Л	Л	И

3)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	И	Л	И	И	Л	Л	И
a2	Л	Л	И	Л	И	И	И	И
a3	И	Л	И	Л	И	И	Л	И
a4	И	И	Л	И	Л	Л	Л	И

4)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	И	Л	И	Л	И	И	Л
a2	Л	И	И	И	Л	И	И	Л
a3	Л	И	Л	И	Л	Л	Л	Л
a4	И	Л	И	Л	Л	Л	Л	Л

5)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	И	Л	И	И	Л	Л	Л
a2	Л	И	И	И	И	Л	Л	И
a3	И	И	Л	Л	И	И	Л	И
a4	И	Л	И	Л	И	Л	Л	Л

6)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	И	Л	И	И	И	И	Л
a2	Л	И	И	И	И	И	И	Л
a3	Л	Л	И	И	И	Л	Л	Л
a4	И	Л	Л	И	И	И	Л	Л

7)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	Л	Л	И	Л	И	И	Л
a2	И	И	Л	Л	Л	И	И	Л
a3	И	И	Л	И	И	И	И	Л
a4	И	И	Л	Л	И	Л	Л	Л

8)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	И	Л	И	Л	И	Л	И
a2	И	Л	Л	И	И	Л	И	Л
a3	Л	И	Л	И	И	Л	Л	И
a4	Л	Л	И	И	И	Л	Л	Л

9)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	Л	Л	Л	Л	Л	Л	Л
a2	И	И	И	И	Л	И	И	Л
a3	Л	И	Л	И	И	И	И	И
a4	Л	Л	Л	И	И	И	Л	И

Решение:

Y

b1

b2

b3

b4

b5

b6

b7

b8

" x P(x, y)

$x P(x, y)

X

" y P(x, y)

X

$ y P(x, y)

a1

a1

a2

a2

a3

a3

a4

a4

2. Предикат R(x,y) определен на множествах: X={a₁,a₂,a₃,a₄,a₅}, Y={b₁,b₂,b₃,b₄,b_5,b₆,b₇,b₈} и имеет таблицу истинности. С помощью кванторов постройте высказывания и определите их истинность:

0)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	Л	Л	Л	Л	И	И	И
a2	И	И	Л	И	И	И	Л	Л
a3	И	И	Л	И	И	Л	Л	Л
a4	Л	Л	Л	И	Л	Л	Л	Л
a5	Л	Л	Л	Л	Л	Л	Л	Л

1)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	И	Л	И	Л	И	И	Л
a2	Л	Л	Л	И	Л	И	Л	Л
a3	И	И	И	И	Л	И	Л	Л
a4	Л	Л	И	И	И	И	И	И
a5	И	Л	Л	И	Л	И	Л	Л

2)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	Л	И	И	И	И	И	И
a2	И	Л	Л	И	Л	Л	Л	И
a3	И	Л	Л	И	Л	Л	Л	И
a4	И	Л	Л	И	И	Л	Л	И
a5	И	Л	И	И	И	И	Л	Л

3)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	И	Л	И	И	Л	Л	И
a2	Л	Л	И	Л	И	И	И	И
a3	И	Л	И	Л	И	И	Л	И
a4	И	И	Л	И	Л	Л	Л	И
a5	И	Л	И	Л	Л	Л	И	Л

4)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	И	Л	Л	Л	Л	И	Л
a2	И	И	И	И	Л	И	И	Л
a3	И	И	И	И	Л	Л	Л	Л
a4	И	Л	И	Л	Л	Л	Л	Л
a5	Л	Л	Л	Л	Л	Л	И	И

5)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	Л	Л	И	И	Л	Л	Л
a2	Л	И	И	Л	И	Л	Л	И
a3	Л	И	Л	Л	И	И	Л	Л
a4	И	Л	И	Л	И	Л	Л	Л
a5	Л	И	Л	И	Л	Л	И	Л

6)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	И	Л	И	И	И	И	И
a2	Л	И	И	И	И	И	И	Л
a3	Л	И	И	И	И	Л	Л	Л
a4	И	Л	Л	И	И	И	И	И
a5	И	Л	Л	И	Л	Л	Л	Л

7)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	Л	Л	И	И	И	И	Л
a2	И	И	Л	Л	Л	И	И	Л
a3	И	И	Л	И	И	И	И	Л
a4	И	И	Л	Л	И	И	Л	Л
a5	И	И	И	Л	Л	Л	Л	Л

8)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	И	И	Л	И	И	И	И	И
a2	И	Л	И	И	И	Л	И	Л
a3	Л	И	Л	И	И	Л	Л	И
a4	Л	И	И	И	И	И	Л	Л
a5	И	Л	Л	Л	Л	Л	Л	Л

9)

X	Y
b1	b2	b3	b4	b5	b6	b7	b8
a1	Л	И	Л	И	Л	Л	Л	Л
a2	И	И	И	И	И	И	И	И
a3	Л	И	Л	И	И	И	И	И
a4	Л	Л	Л	И	И	И	Л	И
a5	Л	Л	Л	И	Л	Л	Л	Л

Решение:

X

" y R(x, y)

X

$ y R(x, y)

a1

a1

a2

a2

a3

a3

a4

a4

a5

a5

Y

b1

b2

b3

b4

b5

b6

b7

b8

" x R(x, y)

$x R(x, y)

3. Предикат А(x,y) определен на множествах: X={a₁,a₂,a₃,a₄,a₅,a₆}, Y={b₁,b₂,b₃,b₄,b₅,b₆,b₇} и задан таблично. С помощью кванторов постройте высказывания и определите их истинность:

0)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	Л	И	Л	И	Л	И	Л
a2	Л	И	И	И	Л	И	И
a3	И	И	Л	И	Л	И	Л
a4	И	И	Л	И	Л	И	Л
a5	Л	И	Л	Л	И	И	Л
a6	И	И	Л	Л	Л	Л	И

1)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	Л	И	Л	И	Л	Л	И
a2	Л	И	И	И	Л	Л	Л
a3	И	И	Л	И	Л	И	И
a4	И	И	Л	И	Л	И	Л
a5	Л	И	Л	И	И	Л	И
a6	Л	Л	Л	Л	Л	Л	Л

2)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	Л	И	Л	И	Л	Л	И
a2	Л	И	И	И	Л	Л	Л
a3	Л	Л	Л	И	Л	Л	И
a4	Л	Л	И	И	И	И	И
a5	Л	И	И	Л	И	И	Л
a6	Л	И	Л	Л	Л	Л	И

3)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	Л	И	Л	И	И	Л	И
a2	И	И	Л	Л	Л	Л	Л
a3	И	И	Л	И	Л	Л	И
a4	Л	И	Л	Л	И	И	И
a5	И	И	Л	И	И	И	Л
a6	Л	И	И	И	Л	И	И

4)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	И	И	Л	И	Л	И	Л
a2	Л	И	Л	И	Л	И	Л
a3	Л	И	Л	И	Л	Л	Л
a4	Л	Л	Л	Л	Л	И	И
a5	И	И	Л	И	И	И	Л
a6	И	Л	И	Л	И	И	И

5)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	И	Л	Л	И	Л	И	Л
a2	Л	Л	Л	И	И	Л	Л
a3	Л	И	Л	И	И	Л	Л
a4	Л	Л	Л	Л	И	Л	И
a5	Л	И	Л	И	И	И	И
a6	Л	Л	Л	Л	Л	Л	И

 

6)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	Л	И	Л	И	Л	Л	И
a2	Л	Л	И	Л	Л	Л	Л
a3	Л	И	Л	И	И	Л	Л
a4	Л	И	И	Л	Л	Л	И
a5	Л	Л	Л	И	И	Л	И
a6	И	И	Л	Л	И	И	И

7)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	И	Л	Л	И	Л	И	Л
a2	Л	Л	Л	И	И	Л	Л
a3	Л	И	Л	И	И	Л	Л
a4	Л	Л	Л	Л	И	Л	И
a5	Л	И	Л	И	И	И	И
a6	Л	Л	Л	Л	Л	Л	И

8)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	И	Л	Л	Л	И	И	И
a2	И	Л	Л	Л	Л	И	И
a3	И	Л	И	И	Л	И	И
a4	И	Л	И	И	Л	И	И
a5	Л	И	И	И	И	И	И
a6	Л	И	Л	Л	Л	Л	И

9)

X	Y
b1	b2	b3	b4	b5	b6	b7
a1	Л	Л	Л	И	Л	И	И
a2	Л	И	Л	Л	И	Л	И
a3	Л	И	Л	Л	Л	И	Л
a4	И	Л	Л	Л	И	Л	Л
a5	И	И	Л	Л	И	И	И
a6	Л	И	Л	Л	Л	Л	И

Решение:

Y	b1	b2	b3	b4	b5	b6	b7
" x A(x, y)
$x A(x, y)

 

 

X	" y A(x, y)		X	$ y A(x, y)
a1			a1
a2			a2
a3			a3
a4			a4
a5			a5
a6			a6
	Высказывание	Значение истинности
	"x "y A(x, y)
	"x$ y A(x, y)
	$ x"y A(x, y)
	$ x$ y A(x, y)
	"y$ x A(x, y)
	$ y"x A(x, y)

Виды форм логики предикатов

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

Пусть P(х), Q(х) и U(x,y) – переменные предикаты. Тогда имеют место равносильности:

Ø$x P(x) º "x ØP(x) Ø"x P(x) º $x ØP(x)

Ø("x P(x)Ú $y Q(y)) º $x ØP(x) & "y ØQ(y) Ø("x P(x) & $y Q(y)) º $x ØP(x) Ú "y ØQ(y)

Ø Ø "x P(x) º "x P(x) Ø Ø $x P(x) º $x P(x)

"x "y U(x, y) º "y "x U(x, y) $x $y U(x, y) º $y $x U(x, y) "x $y U(x, y) ¹ $y "x U(x, y) $x "y U(x, y) Þ "y $x U(x, y)

"x "x Q(x) º "x Q(x) $x $x Q(x) º $x Q(x) "x (P(x) & P(x)) º "x P(x) $x (P(x) Ú P(x)) º $x P(x)

"x P(x) & "y U(y) º "x"y (P(x) & U(y)) "x P(x) & "x U(x) º "x (P(x) & U(x))

$x P(x) Ú $y U(y) º $x$y (P(x) Ú U(y)) $x P(x) Ú $x U(x) º $x (P(x) Ú U(x))

$x P(x) & $x U(x) ¹ $x (P(x) & U(x)) $x P(x) & $x U(x) º $x $ a (P(x) & U(a))

"x P(x) Ú "x U(x) ¹ "x (P(x) Ú U(x)) "x P(x) Ú "x U(x) º "x "a (P(x) Ú U(a))

"x P(x) & $x U(x) º "x$a (P(x) & U(a)) "x P(x) Ú $x U(x) º "x$a (P(x) Ú U(a))

В логике предикатов различают два вида форм: приведенную и предваренную.

Говорят, что формула логики предикатов имеет приведенную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.

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

Алгоритм получения ПНФ:

1. выразите операции импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание;

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

3. для формул, содержащих подформулы вида: "x P(x) Ú "x U(x), $xP(x) & $xU(x), "xP(x) & $xU(x), "xP(x) Ú $xU(x) введите новые связанные переменные;

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

Примеры выполнения заданий

1. Приведите формулу логики предикатов к приведенной форме:

 

2. Приведите формулу логики предикатов к приведенной форме, где x, y, z – вещественные переменные, применив отрицание к формуле:

"y $x ((y ¹ x) Ú Ø"y (x < y) & "z (y - x £ z)).

Ø ("y $x ((y ¹x)Ú Ø"y (x < y) & "z (y - x £ z))) º

º $y "x ((y = x) & "y (x < y) Ú $z (y - x ≥ z))

3. Приведите формулу логики предикатов к предваренной нормальной форме $x"yP(x, y) Ú Ø"x$yQ(x, y).

$x"yP(x, y) Ú Ø"x$yQ(x, y)º $x"yP(x,y) Ú $x"yØQ(x, y) º

º $x("yP(x, y) Ú "yØQ(x, y)) º $x("yP(x, y) Ú "аØQ(x,а)) º

º $x"y"а (P(x, y) Ú "аØQ(x, а)).

Задания для самостоятельного выполнения

4. Приведите формулу логики предикатов к предваренной нормальной форме:

0)

Ø"y $x T(y, x) Ú $y"x Q(y, x);

$x (Ø"y U(y, x) & $z$y L(y, z, x));

"x Ø("y A(x, y) ®$y H(z, x));

Ø"y"z U(y, z) ~ "x $y Q(y, x);

1)

"y Ø($x G(y, x) ® "z $x N(y, x, z));

$x "y (Ø(E(y, x) & $z Q(y, z)));

$t (Ø("y K(y, t) ~ $y $z Q(y, t, z)));

"z"x A(x, z) Ú "y"z Q(y, x);

2)

$y"x M(y, x) & $y"z Q(y, z);

$t Ø("y K(y, t) ®$x $y F(y, x, t));

"z"y Ø($x G(z, y) ~ "x"s N(x, s));

Ø"s$x U(s, x) Ú $y"x Q(y, x);

3)

"y ("m U(y, m) & "x Q(y, x));

"x Ø($y A(x, y) ® (Ø$z"y D(y, z));

$x Ø($y"z P(z, x, y) Ú $z"y K(y, x, z));

$x"y T(y, x) ~ Ø$y"x P(y, x);

4)

"y $z T(y, z) ~ "x "y Q(y, x));

$t Ø ("y U(y, t) Ú $y "x R(y, x));

"x (Ø($y G (y, x) ® Ø"y P(y, x));

"t (Ø$x "y N(y, x) & $y L(y, t));

5)

"y ($x $z F(z, y, x) ® Ø"x Q(y, x));

$x "y (Ø "t U(t, y, x)) Ú Ø"x $y R(y, x);

"z Ø("y A(z, y) & Ø$x $y H(y, x));

$a $y U(y, a) ~ $t $a Q (a, t));

6)

"y Ø($n A(n, y) ® $y "n H(y, n));

Ø"y"m U(y, m) Ú Ø"y"x D(y, x);

"x ($n C(n, x) ~ "t $y Q(y, x, t));

"n"m Ø"y G(n, y, m) & Ø"x$y B(y, x));

7)

"z Ø("y C(z, y) ® $y $t "x Q(t, y, x));

$z "y U(z, y) & $x $z"m F(m, x, z);

"x Ø($y $t A(x, y, t) ~ "y $z Q(y, z));

"y"m U(y, m) Ú Ø"x$y $m K(m, x, y);

8)

"z Ø($x A(x, z) ® $y Ø$z Q(y, z));

"y ("m U(y, m) & Ø$m"x F(y, x, m));

"x Ø("y$z K(x, z, y) ~ $y Q(y, x));

"x Ø("y"t U(t, y, x) Ú Ø$y$t R(y, t));

9)

"t Ø($y $z H(t, y, z) ® $x "y G(y, x));

$x Ø"y U(y, x) & $x $y"z Q(y, z, x);

"y"x $z A(y, x, z) Ú "x$z B(z, x);

$x Ø("y K(y, x) ~ $y$z L(y, x, z)));