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

Практическое занятие №13. Формулы
логики предикатов.

Равносильность формул логики предикатов

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

Пусть 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. используя свойства и законы логики предикатов, вынесите все кванторы перед высказыванием и получите формулу в виде ПНФ.

5.

Дата добавления: 2014-11-20