С эквивалентна А равносильна С эквивалентна В.

9) Опред. Формула А назыв. тавтологией (тождествинно истинно)если она принимает значение 1. При всех значениях в неё переменных. Формула В называется тождественно ложной если она равна 0 при всех значения Х переменных.

С точки зрения алгебры логики тавтологии – это логический законы, так как они принимают истинные значения при любых значениях переменных.

10. Булевой алгеброй ^[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

		ассоциативность
		коммутативность
		законы поглощения
		дистрибутивность
		дополнительность

11. Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.^[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.
12. Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.^[1] Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.

13. Предика́т (n -местный, или n -арный) — это функция с множеством значений (или {ложь, истина}), определённая на множестве . Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный».

Предикат можно связать с математическим отношением: если (m₁,m₂,...,m_n) принадлежит отношению, то предикат будет возвращать на ней 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.

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

Предикат называют тождественно-истинным и пишут:

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д

Примеры

Например, обозначим предикатом EQ(x, y) отношение равенства («x = y»), где x и y принадлежат R (множеству вещественных чисел). В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.

Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y», где множество M — это множество всех людей.

Предикат — это то, что утверждается или отрицается о субъекте суждения.

Операции над предикатами

Предикаты, так же, как высказывания, принимают два значения истинное и ложное, поэтому к ним применимы все операции логики высказываний. Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Логические операции

Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката А(х) В(х), х Х является пересечение множеств истинности предикатов А(х) – Т1 и В(х) – Т2, т.е. Т= Т1 ∩Т2. Например: А(х): «х – четное число», В(х): «х кратно 3». А(х) В(х) – «х – четное число и х кратно 3». Т.е. предикат «х делится на 6».

Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката А(х) В(х) является объединение областей истинности предикатов А(х) В(х).

Отрицанием предиката А(х) называется новый предикат, который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката, х Х является дополнение Т' к множеству Т в множестве Х.

Импликацией предикатов А(х) и В(х) называется новый предикат А(х) В(х), который является ложным при тех и только тех значениях х Т, при которых А(х) принимает значение «истина», а В(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)». Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное число х делится на 4», можно составить предикат: «Если натуральное число х делится на 3, то оно делится и на 4». Множеством истинности предиката А(х) В(х) является объединение множества Т2 – истинности предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).

Кванторные операции

Квантор (все-)общности

Квантор существования

Квантор существования по переменной ₁

 

14. Логические операции над предикатами.

Для предикатов выполнимы следующие операции:

Конъюнкция -этоновый предикат, который принимает значение истинно при тех и только тех значениях из вещественной области, при которых оба предиката и истинны одновременно, и ложно во всех других случаях.

Дизъюнкция -этоновый предикат, который принимает значение ложно при тех и только тех значениях из вещественной области, при которых оба предиката и ложны одновременно, и истинно во всех других случаях.

 

Отрицание предиката - это новый предикат, который принимает значение истинно при всех из вещественной области, при которых предикат принимает значение ложно и наоборот.

15. из х следует у, где х- условие,а у- значение.

Если теорема верна, то истинность высказываний у назыв. необходимость условием для х, а истинность х назыв. достатычным условием для истинности.

С теоремой вида из х следует у связывают 3: 1)Противоположную; 2)Обратную, 3)Обратно противоположную.

1. Противоположной к теореме х следует у назыв. теорема: из х с инверсией следует у с инверсией,в которой условие х и заключение у исходной теоремы заменяется их отрицанием.

2. Обратной к теореме х следует у назыв. теорема: из у следует х, в которой условия и заключение меняются местами.

3.Обратно противоположной теореме из х следует у назыв. теорема из у с инверсией следует х с инверсией. Из справедливости исходной теоремы всегда вытекает справедливость обратно противоположной теоремы. А для обратной и противоположной теорем истинности не следует автоматически из истинности исходной теорем.

3) Метод необходимого и достаточного.

Пусть теорема формулируется: что бы имело место х, необходимо и достаточно у; или а имеет место (истинно) тогда и только тогда, когда имеет место В(истинна).

16.

17. доказательство от противного -метод локазательства теоремы, при котором доказывают не саму теорему, а теорему противоположную обратной. Этот метод применяют тогда, когда прямую теорему доказать или невозможно или очень затруднительно. При этом доказательстве заключение теоремы заменяют отрицанием и рассуждениями к отрицанию условия, то есть к противоркчию, что и доказывает теорему
Пример. Теорема. Из одной точки К к прямой можно провести только один перпендикуляр
Док-во. Пусть из точки К на прямую провели два перепндикуляра КА и КВ. Тогда угол КАВ =90 и угол КВА =90 по определению перпендикуляра Тогда в тр=ке АКВ сумма этих углов уже больше 180, что противоречит теореме о сумме углов тр-ка.. Это противоречие и доказывает истинность первоначального ктверждения