1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества

12. Полнота множества функций. Замыкание множества функций.
Все булевы функции можно условно разделить на функции принадлежащие к замечательным классам и не принадлежащие к ним. Всего существует 5 замечательных классов БФ: 1) Класс функции, сохраняющий константу const=0, Обозначается Т0. БФ – принадлежит классу Т0, если для нее выполняется условие f(0,0,…,0)=0. 2) Класс функции, сохраняющий const=1 – Т1. Функция относится к классу Т1, если для нее выполняется условие f(1,1,…,1)=1. 3) Класс линейных функций обозначается L. БФ называется линейной, если ее можно представить многочленом Жегалкина. 4) Класс двойственных БФ, обозначается S. Пусть f(x1,x2,…,xn) – БФ f(¯x1,¯x2,…,¯xn) называется двойственной заданной функцией f если выполняются следующие условия, т. е. на противоположных наборах значения двойственными являются функции f(x)=x и F(x)=¯x. 5) БФ называется монотонной, если для любых двух оценок списка переменных, таких что < выполняются условия f (x1,x2,…,xn) < f (x1,x2,…,xn). Сравнивать можно только сопоставимые оценки списка переменных.
14. Понятие предиката. Область определения и область истинности предиката.
Предикатом P(x1, x2, … ,xn) – называется функция, переменные которой определены на некотором множестве М, а сама она принимает значение Истины или Лжи, при этом Р – называется предикатный символ, x1, x2, … ,xn – предметные переменные, М – предметная область (область определения предикатов), {И, Л} – область значений. Подмножество Ip<=М предметной области предиката, на элементах которого предикат принимает значение Истины, называется областью истинности предиката.
15. Обычные логические операции над предикатами. Кванторные операции над предикатами.
Над предикатами на множестве М можно проводить логические операции (¯,^,v,→,↔). В результате проведения логических операций появляются новые более сложные предикаты. При определении их значений необходимо пользоваться таблицами истинности логических операций. Определены в логике предикатов 2 специфические операции, называемые навешиванием квантором или связывание кванторами. Квантор общности: «для всех Х выполняется P(x)» — ∀xP(x). Квантор существования: «существуют х, для которых выполняется Р(х)» — ∃хР(х).