Элементарные булевы функции и их свойства

Алгебра высказываний

Высказывание – это утверждение о котором можно сказать истинно оно или ложно. Высказывания будем обозначать малыми и большими буквами лат. алфавита. Предполагается, что имеется некоторый начальный набор высказываний, которые будем называть простейшими и обозн. малыми буквами. Если высказывание а истинно, то пишем а=1, а если ложно а=0. Из простейших выск. строятся сложные с помощью союзов: и, или, не, связки: если – то. Сложны выск. обозн. большими буквами(A,B,C…). Если сложное выск. А построенное из простых выск. а₁,а₂…а_n то пишем А(а₁,а₂…а_n) Опр.1 Отрицанием выск. а наз. выск. обозн. а‾, которое истинно если а ложно и ложно если а истинно. Опр2. Конъюнкцией 2 выск. а и b наз. выск. аb которое истинно когда оба. выск. истинны и ложно во всех остальных случаях. Опр3. Дизъюнкция двух 2 выск. а и b наз. выск. аVb которое истинно тогда и т.т., когдахотя бы одно из выск. истинно. Опр4. Импликацией 2 выск. а и b наз. выск a b которое ложно тогда и т.т., когда а - истинно, а b – ложно. Т.е a b=0 только при а=1, b=0. Опр5. Эквивалентностьюдвух 2 выск. а и b наз. выск. а~b которое истинно тогда и т.т., когда а и b одновременно истинны или ложны. Опр6. А(а₁,а₂…а_n) и B(а₁,а₂…а_n), эти выск. наз. Равносильными если они принимают одинаковые истинные значения при соотв. Наборах истиностных значений входящих в них переменных, обозн. А≡B.

Булевы функции

Пусть E={(0,1}. Опр. Пусть A и B - 2 непустых множества, декартовым произведением множеств A и B наз. новое мн-во A×B, которое состоит из всевозможных упорядоченных пар вида: A×B={(a,b) | a A, b B}. Из определения декартового произв. следует, что упор. Пара (а,b)=(c,d) тогда и только тогда, когда a=c, b=d, т.е соответствующие компоненты пар равны. Пусть А₁,А₂,….А_n не пустые множества, А₁×А₂...×А_n={(а₁,а₂…а_n) | a_i A_i, i=1..n}, которое по опр. состоит из всевозможных наборов длины n. Из опр. декартового произв. мн-в А₁,А₂,….А_n следует, что упорядоченный набор а₁,а₂…а_n равен упор. набору b₁,b₂…b_n т.и.т.т., когда а_i=b_i, т.е равны соотв. компоненты этих двух упорядоченных наборов. Если A_i =A, то А×А...×А= Aⁿ и называют n-й декартовой степенью мн-ва A. Пусть n – нат. число, рассм. Eⁿ={(а₁,а₂…а_n) | a_i {0;1}, i=1..n} Опр. Отображение f мн-ва Eⁿ в мн-во E наз. булевой функцией, а точнее булевой функцией от n переменных; Утв1. Число булевых ф-ций от n переменных равно 2 в степени 2n.

Элементарные булевы функции и их свойства

Основные булевы функции: 1)f₁(x)=0, x E – “константа 0” 2)f₂(x)=1, x E – “константа 1” 3)f₃(x)=x, x E – ”тождественная функция“ 4)f₄(x)=x‾, x E – ”отрицание x“ 5)f₅(x₁,x₂)=x₁x₂– ”конъюнкция x₁ и x₂“ 6)f₆(x₁,x₂)=x₁V x₂– ”дизъюнкция x₁ и x₂“ 7)f₇(x₁,x₂)=x₁ → x₂– ”x₁ импликация x₂“ 8)f₈(x₁,x₂)=x₁ ~ x₂– ”x₁ эквивалентность x₂“ 9)f₉(x₁,x₂)=x₁ + x₂– ”сложение по модулю 2 “ 10)f₁₀(x₁,x₂)=x₁ | x₂– ”штрих Шефера (антиконъюнкция) “ 11)f₁₁(x₁,x₂)=x₁ x₂– ”стрелка Пирса (антидизъюнкция) “ Основные эквивалентности формул: Пусть означает ,V,+ 1) (x₁ x₂ ) x₃=x₁ (x₂ x₃) – ассоциативность операции 2) x₁ x₂= x₂ x₁ – коммутативность операции 3) = _{1 2} ; = _{1 2} – законы де Моргана. 4) =х – двойное отрицание, x₁ →x₂= ₁ V x₂ 5) (x₁V x₂) x₃=x₁ x₃V x₂ x₃ ; (x₁ x₂) x₃=(x₁ x₃) (x₂ V x₃) – дистрибутивности связывающие конъюнкцию и дизъюнкци 6)x₁V(x₁ x₂)=x₁; x₁ (x₁ x₂)=x₁ – законы поглощения. 7) xVx=x; x x=x – законы идемпатентности 8) x =0 – закон противоречия; 9) x V =1 – закон исключения третьего.