2. Придумайте логическую функцию от двух переменных, и найдите для неё двойственную функцию.
3. Дайте определение самодвойственной функции.
4. Придумайте логическую функцию от трёх переменных, и проверьте, задаёт ли она самодвойственную функцию.
5. Какая система булевых функций называется полной?
6. Дайте определение классов Поста.
7. Сформулируйте теорему Жегалкина.
8. В каком случае полином Жегалкина называется линейным, нелинейным?
9. Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиома булева кольца и равенства, выражающие операции через операции этого булева кольца. Перечислите эти равенства.
10. Сформулируйте теорему Поста.
11. В каком случае система булевых функций называется базисом?
12. Найти полином Жегалкина для булевой функции, заданной вектором значений (1011 0100). Определить к каким классам Поста принадлежит функция.
13. Проверить с помощью теоремы Поста полноту следующих систем булевых функций: . Какие из указанных систем образуют базис?
14. Определить, к каким классам (константы нуля, константы единицы, самодвойственных функций, линейных функций, симметрических функций) относится функция следующего вида. Постройте полином Жегалкина для функций:
1) .
2)
3) .
4)
5) .
6) .
7) .
8) .
9) .
10) .
11) .
12) .
В логике высказываний высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или логичности, то есть не структура, ни их содержание не рассматриваются. В тоже время в науке и практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний. Следовательно, логика высказываний оказывается недостаточной в анализе многих рассуждений. В связи с этим возникает необходимость в расширении логики высказываний, построении такой логической системы, в рамках которой логика высказываний рассматривается как элементарная. Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.
Логика предикатов расчленяет элементарное высказывание на субъект (подлежащее и дополнение в предложении) и на предикат (сказуемое или определение). Субъект – о чём утверждается в высказывании. Предикат – это то, что утверждается в субъекте.
Если «семь» заменить на переменную х, то получим высказывательную формулу - «х – простое число».
Предикат - функция P типа Мn→ B, где B = {0,1}, М – произвольное множество, т.е. функция Р, сопоставляющая вектору (m1,m2,....,mn) значение 0 или 1.
Множество М называется предметной областью предиката Р(m1,m2,....,mn); m1,m2,....,mn- предметными переменными, Р – предикатным символом. Употребление выражения: n – местный предикат на множестве М; число n называется местностью предиката.
В более общем смысле предикатом называется отображение Р: M1×M2 ×.... × Mn → B, где Mi могут быть различными множествами.
Прямое произведение M1 × M2 × ... × Mn будем называть областью определения предиката Р.
Область истинности предиката Р – подмножество IpМnпредметной области предиката Р, на элементах которого значения предиката равны 1.
Другими словами, множество М, на котором определён предикат Р(х) называется областью определения предиката, а множество всех элементов , при которых предикат принимает значение истины, называется множеством истинности предиката P(x): .
Пример 9.2.
1) Одноместный предикат Р(Х) на множестве натуральных чисел: «при делении на 3 число Х дает остаток 2».
Область истинности – множество чисел вида 3n + 2 (n = 0,1,2,….).
2) Двуместный предикат Q(X,Y): при делении на 3 число Х дает остаток Y. Предметная область для Q(X,Y) – множество пар (a,b), где a и b – натуральные числа, причем b {0,1,2}. Область истинности показана на рис. 9.1.
Рис.9.1
3) Трехместный предикат R(X,Y,Z): при делении на Z число X дает остаток Y. Предметная область – множество троек (X,Y,Z), где X,Y,Z N, Z ≠ 0, 0 ≤ Y ≥ Z. Область истинности – множество целочисленных точек трехмерного пространства в I октанте, если при некотором k выполнено равенство X = k*Z + Y.
4) 4-местный предикат Р(λ,L,M,N): «плоскость λ содержит точки L, M, N». Для плоскости λ =3X - 2Y + 4Z + 7=0 и точек L (-3,-5,-2), M (5,13,1), N (7,-4,-9) предикат Р равен 1. Если же вместо точки М(5,13,1) взять точку М (2,6,0), то Р = 0.
