Дискретная математика

55 Функция (х&у) называется конъюнкцией х и Выражение «(xtS^)» читается «х и у» и эту функцию можно интерпретировать как соединение двух высказываний х,ус помощью союза ли». Функция (xvy) называется дизъюнкцией х и у. Выражение <((х'^)» читается «х нли у» и эту функцию можно интерпретировать как соединение двух высказываний <v, у связкой «или», где «или» понимается в соединительном (хотя бы одно), а не разделительном (либо-либо) смысле. Функция (х=>у) называется имтикаг^ией х и у. Выражение «.(х=:>у)» читается «если х, то у» и эту функцию можно интерпретировать как образование из двух высказываний нового высказывания; «если х, то у». При этом X называется посъшкой, & у заключением. Функция (х = у) называется эквивалентностью. Выражение «(х можно читать <ос эквивалентно >>». Функция fx+yjназывается сложением по модулю два. Функции (х1у) и (xi у) называются штрихом Шеффера и стрелкой Пирса соответственно. Используя введенные функции, можно строить более сложные булевы функции с помощью операций суперпозиции функций, т. е. подстановки функций в функцию, например; (1(х £ у)), ((x=>y)&(x^z)), ((xSiy)=>(lz)) и т. п. Значения полученных функций можно определять по таблицам истинности. Таблица истинности функции от одного аргумента имеет две строки, от двух переменных - четыре, от трех переменных - восемь строк, В общем случае таблица истинности булевой функции от п переменных имеет ровно 2'' строк, ибо добавление каждой повой переменной удваивает число строк. Покажем, что число различных булевых функцш от п переменных равно Л/ = 2" , Булева функция f(xux2,:.,xn) принимает значения О либо 1 в зависимости от значений переменных х;,Х2,,,„х„. Число различных наборов значений переменных кахс известно, равно 2". На каждом из 2" различных наборов функция f(xi,x2,...,x^ может принимать одно из двух значений. Следовательно, число различных булевых функций от п 2" аргументов будет равно 2 . С ростом п число N булевых функций от п аргументов резко растет. Например: для п=1 Я=4; для и=2 7^=16; для и=3 N-256-, для п=5 N - более четырех миллиардов. Переменная х^ (7< к<п) функции/f'x;,x2j---.^:J называется фиктивной или несущественной, если значение этой функции не меняются при изменении значений х^. Например, (xv(x&y)) ~ х, следовательно, у является фиктивной переменной для функции/('х.>')=('х\/('хс&:;^^^. Булеву функцию можно задать с помощью таблицы, формулы (аналитически), графика и т,п. Графически булеву функцию f(xi,x2,...,xj задают с помощью и-мерного куба след5тощим образом. Считаем наборы значений переменных х/,х2,...,х„ вершинами и-мерного куба. Те вершины, на которых булева функция равна единице, помечаем точкой или звездочкой, остальные вершины оставляем без пометок. Например, функции (х=ру), (х=у)