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

↑

▷ Содержание

⇐ ПредыдущаяСтр 8 из 9Следующая ⇒

Все логические операции логики высказываний справедливы и для предикатов (отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция). Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. В математической логике приписывание квантора к формуле называется связыванием, а переменную, к которой он относится, называют связанной иначе свободной. Например, в предикате "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 ÎX:

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

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

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

0)

1)

2)

3)

4)

5)

6)

7)

8)

9)

Решение:

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

0)

1)

2)

3)

4)

5)

6)

7)

8)

9)

Решение:

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

0)

1)

2)

3)

4)

5)

6)

7)

8)

9)

Решение:

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

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

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

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

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

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

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

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)));

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии