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

9 Понятие булевой функции (функции алгебры логики). Способы задания булевой функции.
Булевой функцией f(x1, x2, …, xn), называется произвольная n-местная функция, аргумента которой {x1, x2, …, xn} є {0,1} и сама функция принимает значения f= {0,1}, где 0 – ложь, 1 – истина. Булеву функцию можно задать одним из следующих способов: А) аналитический – с помощью формулы. Для булевых функций сохраняются логические операции таблицы истинности логических операций и основные равносильности логики высказываний. Поэтому любую формулу логики можно считать и булевой функцией. Булева функция может быть задана таблицей в которой указываются оценки списка переменных и значения функции. Б) графический – можно изобразить одноместные, 2-местные, 3-местные булевы функции. В) Представление БФ формулой логики.
10. Проблема представления булевой функции в виде формулы логики.
Представление БФ формулой логики. Теорема: пусть f — k-местная БФ (k=>1). Если (f≠0), не равна тождественно 0, то существует такая формула логики f(x1,x2, …,xk) и находящаяся в СДНФ относительно списка переменных, что F выражает f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов. Теорема2: Пусть f(x1,x2, …,xk) – k-местная БФ, если f≠1, то существует такая формула логики зависящая от того же списка переменных и находится в СКНФ, относительно этого списка, что F выражает f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.
11. Многочлен Жегалкина.
Многочлен Жегалкина называется многочлен, являющийся суммой постоянных величин 0 или 1, и различных одночленов, в которой все переменные входят 1-ой степени. Алгоритм представления БФ многочленом Жегалкина: а) упрощение БФ с помощью основных равносильностей логики высказываний; б) представление полученной упрощенной формулы в СДНФ; в) замена логических операций, операциями математики; г) приведение полученного выражения к форме многочлена Жегалкина. 2 способ: а) построить таблицу истинности для заданной БФ; б) выбрать из таблицы строки, где функция принимает 1; в) Построить СДНФ; г) заменить логические операции математическими и упростить полученное выражение.