Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний. Логическое выражение — составные высказывания в виде формулы. Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак « = ».
1. П одсчитать количество переменных n в логическом выражении; 2. О пределить число строк в таблице по формуле m=2 n, где n — количество переменных; 3. П одсчитать количество логических операций в формуле; 4. У становить последовательность выполнения логических операций с учетом скобок и приоритетов; 5. О пределить количество столбцов: число переменных + число операций; 6. В ыписать наборы входных переменных; 7. П ровести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью. Алгоритм построения таблицы истинности
1. Р азделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»; 2. Р азделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»; 3. П родолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа. Заполнение таблицы
_ _ _ Для формулы A ^ (B v B ^ C) постройте таблицу истинности. Количество логических переменных 3, следовательно, количество строк — 2 3 = 8. Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8. Пример 1. A B C __ B __ C __ __ B^C __ __ BvB^C __ __ A^( BvB^C ) 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1
Определите истинность логического выражения _ _ F(А, В) = (А v В) ^ (А v В) . 1. В выражении две переменные А и В (n=2). 2. m строк =2 n, m=2 2 =4 строки. 3. В формуле 5 логических операций. 4. К столбцов =n+5=2+5=7 столбцов. Пример 2 A B __ A __ B AvB __ __ AvB __ __ ( AvB )^( AvB ) 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 0 0 Ответ: F(0,1)=1 и F(1,0)=1.
Простой конъюнкцией или конъюнктом называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Простая конъюнкция полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз; монотонная, если она не содержит отрицаний переменных. Дизъюнктивная нормальная форма, ДНФ — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов. Пример ДНФ: f ( x, y, z )=( x ∧ y )∨( y ∧ z )
Совершенная дизъюнктивная нормальная форма, СДНФ — ДНФ, удовлетворяющая условиям: в ней нет одинаковых простых конъюнкций, каждая простая конъюнкция полная. Пример СДНФ: _ _ f( x,y,z )=( x∧y∧z )∨( x∧y∧z ) Алгоритм построения СДНФ по таблице истинности В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание. Все полученные конъюнкции связываем операциями дизъюнкции.
Построение СДНФ для медианы от трех аргументов 1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1. Пример 3 X Y Z (X,Y, Z) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание. Пример 3 X Y Z (X,Y, Z) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 __ (X^Y^Z) 1 0 0 0 1 0 1 1 __ (X^Y^Z) 1 1 0 1 __ (X^Y^Z) 1 1 1 1 (X^Y^Z) 3. Все полученные конъюнкции связываем операциями дизъюнкции: _ _ _ ⟨ X, Y, Z ⟩=( X ∧ Y ∧ Z )∨( X ∧ Y ∧ Z )∨( X ∧ Y ∧ Z )∨( X ∧ Y ∧ Z )
Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Простая дизъюнкция полная, если в неё каждая переменная (или её отрицание) входит ровно один раз; монотонная, если она не содержит отрицаний переменных. Конъюнктивная нормальная форма, КНФ — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. Пример КНФ: f( X, Y, Z )=( X ∨ Y )∧(Y∨Z)
Совершенная конъюнктивная нормальная форма, СКНФ — это такая КНФ, которая удовлетворяет условиям: в ней нет одинаковых простых дизъюнкций каждая простая дизъюнкция полная Пример СКНФ : _ _ : f ( X, Y, Z )=( X ∨ Y ∨ Z )∧( X ∨ Y ∨ Z ) Алгоритм построения СКНФ по таблице истинности В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 0. Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 0, то в дизъюнкцию включаем саму переменную, иначе ее отрицание. Все полученные дизъюнкции связываем операциями конъюнкции.
Построение С К НФ для медианы от трех аргументов 1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 0. Пример 4 X Y Z (X,Y, Z) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 0, то в дизъюнкцию включаем саму переменную, иначе ее отрицание. Пример 3 X Y Z (X,Y, Z) 0 0 0 0 ( XvYvZ ) 0 0 1 0 __ ( XvYvZ ) 0 1 0 0 __ ( XvYvZ ) 0 1 1 1 1 0 0 0 __ ( XvYvZ ) 1 0 1 1 1 1 0 1 1 1 1 1 3. Все полученные дизъюнкции связываем операциями конъюнкции. _ _ _ ⟨ X, Y, Z ⟩= ( X v Y v Z )∧ ( X v Y v Z ) ∧ ( X v Y v Z ) ∧ ( X v Y v Z )
