Дискретная математика 04
1. С помощью построения таблиц истинности доказать формулы:
= 
Построим таблицу истинности для правой и левой части формулы, принимая обозначения 0 – ложь, 1 – истина. 
Так как значения правой и левой части на одинаковых наборах переменных совпадают, то формула
=
Является тавтологией, то есть верна для любых значений переменных.
Ответ: формула является тавтологией.
2. С помощью построения таблиц истинности проверить, является ли формула тавтологией:
Формула является тавтологией, если на всех наборах переменных принимает значение «истина».
Построим таблицу истинности
Данная формула является противоречием, то есть ложна для любых наборов переменных.
Ответ: формула не является тавтологией.
3. Записать с помощью кванторов следующие утверждения и их отрицания.
Функция 
достигает наибольшего значения на отрезке 
в точке 
Решение:
- исходное утверждение.
Отрицание утверждения:
Функция не достигает наибольшего значения на отрезке в точке .
.
Ответ: - утверждение, - отрицание утверждения.
4. Установить и изобразить графически область истинности предиката: 
, 
Решение:
Область определения предиката – числовая плоскость . Аргументы предиката – пары чисел (х, у). Условие задаёт прямую на плоскости у = х – 1.
Область истинности предиката - это прямая у = х – 1, на рисунке изображена линией синего цвета.
5. Пусть 
– натуральное число. Даны следующие утверждения:
· 
– “число кратно 5”;
· 
– “число кратно 2”;
· 
– “число кратно 4”;
· 
– “число кратно 10”;
· 
– “число кратно 20”.
Укажите, какое высказывание истинно, какое ложное
Решение:
- предикат, обозначающий “число не кратно 5”;
- предикат, обозначающий “число не кратно 20”.
- высказывание «если произвольное натуральное число не кратно 5, то оно также не кратно 20».
Так как условие кратности 5 является необходимым для выполнения условия кратности 20, то высказывание является истинным.
Ответ: высказывание истинно.
6. Построить вывод формулы
Решение:
Рассмотрим правила введения и удаления отрицания:
; 
.
Здесь G – некоторый набор формул (возможно, пустой), Х – одна формула.
Согласно закону исключённого третьего, 
или 
. Подставим вместо Х формулу ØА, получим
или 
. Обозначим во второй формуле 
, тогда получим 
. Воспользуемся правилом удаления отрицания
.
Отсюда, возвращаясь к А, получаем
.
И, по теореме дедукции, 
или .
Формула доказана.
7. Методом резолюций доказать теоремы
├
Решение:
Приведем отрицание доказываемого высказывания к конъюнктивной нормальной форме (КНФ):
Используя тавтологию 
, получим
Учитывая тавтологию 
и раскрывая скобки, получим
Далее преобразуем при помощи закона де Моргана: 
.
Получили КНФ отрицания исходного высказывания. Используя КНФ как допущение некоторой секвенции, по правилу расщепления получим список допущений:
1) А;
2) 
;
3) 
.
Список содержит явное противоречие – строки 1 и 2. Следовательно, отрицание исходного высказывания является противоречием. Тогда само высказывание – теорема (тавтология), что и требовалось доказать.
8. Определить значение высказывания, полученного из трехместного предиката на множестве 
.
, 
Решение:
Высказывание может быть истинным, если x<z, и ложным в противном случае, потому что x, y,z – натуральные числа и, соответственно, y≥1. Высказывание, которое на одних значениях переменных принимает значение «истинно», а на других – «ложно», называется выполнимым.
В приведенном случае высказывание ложно, потому что не выполняется для произвольных значений x, z. Например, ложно для x=5, z=4.
Ответ: высказывание ложно.
9. Доказать, что первая формула логически влечет вторую формулу.
; 
Решение:
Требуется доказать ╞ .
Применим теорему дедукции: если G, S ╞ V, то G╞ S→V. Получим
╞ 
.
Справа от знака ╞ (выводимо) записана в точности аксиома 8 Гильберта логики высказываний, что есть тавтология. Следовательно, первая формула логически влечет вторую формулу.
Утверждение доказано.
10. Доказать, что формула является тавтологией, без построения таблицы истинности. Во всех формулах выделить всевозможные подформулы.
.Решение:
Подформулы исходной формулы, всего 5 подформул: 
.
Проведём преобразования исходной формулы, последовательно используя тавтологию .
.
Далее преобразуем при помощи закона де Моргана:
Учитывая закон снятия двойного отрицания и раскрывая скобки, получим
Используем закон идемпотентности 
для первой скобки
Учтём закон поглощения 
и получим запись закона исключённого третьего (аксиома 11 Гильберта):
.
Формула доказана.
| < Предыдущая | Следующая > |
|---|
