Навигация:

Главная Случайная страница Обратная связь ТОП Интересно знать Избранные Новые материалы

Топ:

Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...

Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...

Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...

Интересное:

Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...

Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...

Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...

Дисциплины:

Автоматизация Антропология Археология Архитектура Аудит Биология Бухгалтерия Военная наука Генетика География Геология Демография Журналистика Зоология Иностранные языки Информатика Искусство История Кинематография Компьютеризация Кораблестроение Кулинария Культура Лексикология Лингвистика Литература Логика Маркетинг Математика Машиностроение Медицина Менеджмент Металлургия Метрология Механика Музыкология Науковедение Образование Охрана Труда Педагогика Политология Правоотношение Предпринимательство Приборостроение Программирование Производство Промышленность Психология Радиосвязь Религия Риторика Социология Спорт Стандартизация Статистика Строительство Теология Технологии Торговля Транспорт Фармакология Физика Физиология Философия Финансы Химия Хозяйство Черчение Экология Экономика Электроника Энергетика Юриспруденция

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

2019-05-27

1610

0.00 из 5.00 0 оценок

Заказать работу

Содержание

⇐ ПредыдущаяСтр 13 из 13

Определение 1

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

Определение 2

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

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности:

6. .

10.

11.

12.

13.

14.

15.

Например:

Предикат Мать(x,y) означает, что x является матерью для y, тогда Мать(x, y) означает, что у каждого человека есть мать, – истинное утверждение.

Мать(x, y) означает, что существует мать всех людей, что является другим утверждением, истинность которого зависит от множества значений, которые могут принимать y: если это множество братьев и сестер, то оно истинно, а в противном случае оно ложно.

Таким образом, перестановка кванторов всеобщности и существования может изменить смысл и значение выражения.

Законы логических операций

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. . .

13. .

14. .

15.

16. .

17. .

18. .

19. .

20. .

21. .

22. .

23.

Примеры решения задач

Пример 1. Найти отрицание следующих формул:

А) ;

Б) ;

В)

Решение

А) ;

Б) ;

В)

Пример 2. Доказать равносильность:

Решение

Для доказательства равносильности достаточно рассмотреть два случая:

1. Пусть предикаты А(х) и В(х) тождественно ложны. Тогда будет ложным и предикат . При этом будут ложными высказывания и .

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

Следовательно, .

Пример 3. Доказать равносильность:

Решение

Рассмотрим два случая:

1. Пусть высказывание С ложно. Тогда для любого предиката будет ложным высказывание и предикат , и, следовательно, высказывание . Значит, в этом случае обе исходные формулы тождественно ложны.

2. Пусть теперь высказывание С истинно. Тогда, очевидно, значения исходных формул будут целиком зависеть от значений предиката А(х). Если А(х) – тождественно истинный предикат, то будет тождественно истинным и предикат , и, следовательно, будут тождественно истинными высказывания , , , т. е. тождественно истинны и исходные формулы.

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

Пример 4. Доказать, что формула

является общезначимой.

Решение

Считая, что формула А определена на любой области М, проведем равносильные преобразования:

Т. е. формула А тождественно истинна для любых одноместных предикатов Р(х) и Q(х) и в любой области.

Варианты заданий

Задание1

Выписать формулу по заданной функциональной схеме.

Задание2

Построить СДНФ, упростить формулу и построить схему.

Задание 3

Запишите с помощью кванторов заданное утверждение.

Значения			Варианты
Значения			1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
X1	X2	X3	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F
0	0	0	0	0	1	0	1	1	1	1	0	0	1	1	0	0	1
0	0	1	0	0	1	0	0	0	1	1	0	1	1	0	0	1	0
0	1	0	0	0	1	1	0	0	0	1	1	0	0	1	0	0	1
0	1	1	0	1	0	1	0	1	0	0	0	1	0	1	0	1	0
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	0	1
1	0	1	1	1	1	0	0	0	1	1	0	0	0	0	0	1	0
1	1	0	1	0	0	1	0	0	0	0	1	0	1	0	1	0	0
1	1	1	0	1	0	0	0	0	0	0	1	0	1	0	1	0	0

Вариант 1

2. Запишите с помощью кванторов следующее утверждение:

“Существует x, такой что x > y ”.

Вариант 2

2. Запишите с помощью кванторов следующее утверждение:

“Не существует x, такой что x > y”.

Вариант 3

