Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

С помощью кванторов общности и существования постройте высказывания и определите их истинность. 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; Просмотров: 442; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.