Республики казахстан южно-казахстанский экономико-технологический

Таблица истинности. Диаграмма Эйлера-Венна.

Таблица истинности
Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания.

Составное высказывание в алгебре логики записываются с помощью логических выражений. Для любого логического выражения достаточно просто построить таблицу истинности.

Алгоритм построения таблицы истинности:

1. 
   подсчитать количество переменных n в логическом выражении;
   
2. 
   определить число строк в таблице, которое равно m = 2ⁿ;
   
3. 
   подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;
   
4. 
   ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;
   
5. 
   заполнить столбцы входных переменных наборами значений;
   
6. 
   провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.
   

Наборы входных переменных рекомендуется перечислять следующим образом:

а) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

б) разделить колонку второй переменной на четыре части и заполнить каждую четверть чередующимися группами нулей и единиц, начиная с группы нулей;

в) продолжать деление колонок значений последующих переменных на 8, 16 и так далее частей и заполнение их группами нулей или единиц до тех пор, пока группы нулей и единиц не будут состоять из одного символа.

Пример: для формулы A&(Bv&) построить таблицу истинности.

Кол-во логических переменных  3 (A,B,C), следовательно, кол-во строк в таблице истинности должно быть 2 в третьей степени = 8.

Кол-во логических операций в формуле 5, следовательно, количество столбцов должно быть 3 + 5 = 8.

A	B	C			&	BV (&)	A&(B V &)
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

В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений.

1. 
   Закон двойного отрицания:
   

Двойное отрицание исключает отрицание.

2. 
   Переместительный (коммутативный закон):
   
   • 
     для логического сложения:
     

• 
  для логического умножения:
  

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

В обычной алгебре a + b = b + a, a * b = b * a.

3. 
   Сочетательный (ассоциативный) закон:
   
   • 
     для логического сложения:
     

• 
  для логического умножения:
  

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

В обычной алгебре (a + b) + c = a + (b + c) = a + b + c,

(a * b) * c = a * (b * c) = a * b * c.

4. 
   Распределительный (дистрибутивный) закон:
   
   • 
     для логического сложения:
     

• 
  для логического умножения:
  

Определяет правило выноса общего высказывания за скобку.

В обычной алгебре справедлив распределительный закон только для сложения: (a + b) * c = a * c + b * c.

5. 
   Закон общей инверсии (закон де Моргана):
   
   • 
     для логического сложения:
     

• 
  для логического умножения:
  

6. 
   Закон идемпотентности (от латинских слов idem – тот же самый и potens – сильный; дословно – равносильный):
   
   • 
     для логического сложения:
     

• 
  для логического умножения:
  

Закон означает отсутствие показателей степени.

7. 
   Законы исключения констант:
   
   • 
     для логического сложения:
     

• 
  для логического умножения:
  

8. 
   Закон противоречия:
   

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. 
   Закон исключения третьего:
   

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе – ложно, третьего не дано.

10. 
    Закон поглощения:
    
    • 
      для логического сложения:
      

• 
  для логического умножения:
  

11. 
    Закон исключения (склеивания):
    
    • 
      для логического сложения:
      

• 
  для логического умножения:
  

12. 
    Закон контрапозиции (правило перевертывания):
    

Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

(&)v(&A)
Согласно распределительному закону для логического сложения:

&(vA)
Согласно закону исключения третьего и закона исключения констант:

& 1 =
Полученную левую часть приравняем правой:

= B
Окончательно получим:

X =