Логические выражения и логические операции

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквивалентность.

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

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

количество строк = 2n + строка для заголовка,

n - количество простых высказываний.

2. Определить количество столбцов:

количество столбцов = количество переменных + количество логических операций;

 

• определить количество переменных (простых выражений);
• определить количество логических операций и последовательность их выполнения.

3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.

Пример: Составить таблицу истинности логического выражения:

D = ¬ А & (B Ú C).

Решение: Ù

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 23 +1 = 9.

2. Определить количество столбцов:
• простые выражения (переменные): А, В, С;
• промежуточные результаты (логические операции):  
  ¬ А - инверсия (обозначим через E);  
  B Ú C - операция дизъюнкции (обозначим через F);  
  а также искомое окончательное значение арифметического выражения:  
  D = ¬ А & (B Ú C). т.е. D = E & F - это операция конъюнкции.
3. Заполнить столбцы с учетом таблиц истинности логических операций.

A	B	C	E	F	E & F
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	0	1	0
1	1	1	0	1	0

 

Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции 
Z(X,Y):

X	Y	Z
0	0	1
0	1	0
1	0	1
1	1	0

Составить логическую функцию для заданной таблицы истинности.

Правила построения логической функции по ее таблице истинности:

1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.

Решение.

1. В первой и третьей строках таблицы истинности значение функции равно 1.
2. Так как строки две, получаем дизъюнкцию двух элементов: ( ) V ( ).
3. Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y: (X & Y) V (X & Y).
4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию: 
   Z (X, Y) =(¬ X & ¬Y) V (X & ¬Y).

3. Законы  логики и правила преобразования  логических выражений

1. Закон двойного отрицания (двойное отрицание исключает отрицание):

А =  .

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

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

3. Сочетательный (ассоциативный) закон:
• для логического сложения: (А Ú B) Ú C = A Ú (B Ú C);
• для логического умножения: (A & B) & C = A & (B & C).

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

4. Распределительный (дистрибутивный) закон:
• для логического сложения: (А Ú B) & C = (A & C) Ú (B & C);
• для логического умножения: (A & B) Ú C = (A Ú C) & (B Ú C).

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

5. Закон общей инверсии (законы де Моргана):
• для логического сложения:  =   & ;
• для логического умножения:  =    Ú 
6. Закон идемпотентности (от латинских слов idem — тот же самый и potens — сильный; дословно — равносильный):
• для логического сложения: А Ú A = A;
• для логического умножения: A & A = A .

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

7. Законы исключения констант:
• для логического сложения: А Ú 1 = 1, А Ú 0 = A;
• для логического умножения: A & 1 = A, A & 0 = 0.
8. Закон противоречия:
• A &   = 0.

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

9. Закон исключения третьего:
• A Ú   = 1.

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

10. Закон поглощения:
• для логического сложения: А Ú (A & B) = A;
• для логического умножения: A & (A Ú B) = A.

Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие - основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

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

Упрощение формул.

Пример 1. Упростить формулу (А Ú В) & (А Ú С).

Решение:

1. Раскроем скобки: (А Ú В) & (А Ú С) = A & A Ú A & C Ú B & A Ú B & C;
2. По закону идемпотентности A & A =A, следовательно,  
   A & A Ú A & C Ú B & A Ú B & C = A Ú A & C Ú B & A Ú B & C;
3. В высказываниях А и А & C вынесем за скобки А и используя свойство А + 1= 1, получим  
   A Ú A & C Ú B & A Ú B & C = A & (1 Ú C) Ú B & A Ú B & C = A Ú B & A Ú B & C;
4. Аналогично предыдущему пункту вынесем за скобки высказывание А.  
   A Ú B & A Ú B & C = A & (1 Ú B) Ú B & C = A Ú B & C.

Таким образом, мы доказали закон дистрибутивности.

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

Пример 2. Упростить выражения   так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.

Решение:  
 

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

Рассмотрим пример логического выражения.

(X * Y = 5  или   X * Y  = 4 )  И  (X * Y ≠ 5   или  X * Y ≠  4)

Подставим в выражение значения  x=2,  y=2  

(2 * 2 = 5 или  2 * 2 = 4)  И   (2 * 2 ≠ 5 или  2 * 2 ≠ 4)

Выделяем простые высказывания и связки 

( A  или  B )  И  (¬A  или ¬B )  

Запишем выражение логической функции

F =   ( A  V  B )  &   (¬A  V ¬B ) 

Подставим в  функцию формальные значения высказываний.

F  =  ( 0  V  1)  &  (1  V  0) = 1 & 1    =   1   -  для данных условий результирующим значением функции является истина

Для выяснения поведений функций в любых ситуациях строят  для них таблицы истинности.

Количество проверяемых комбинаций равно    2n 

- где n – количество логических переменных.   

Рассмотрим следующую функцию:     F =   ( A  V  B )  &   (¬A  V ¬B )  

А	B	A V B	¬A	¬B	¬A  V ¬B	F
0	0	0	1	1	1	0
1	0	1	0	1	1	1
0	1	1	1	0	1	1
1	1	1	0	0	0	0

 

Пример 1. 
 
Постановка условия:  Если придет Вася или Коля и мама разрешит, то пойду гулять.  
 
Обозначим :

	Приход Васи	A
	Приход Коли	B
	Разрешение мамы	C

 
Запишем логическую функцию F = ( A V B )  &  C  
 
Составим таблицу истинности 
 

A	B	A V B	C	( A V B )  &  C
0	0	0	1	0
0	0	0	0	0
1	0	1	1	1
1	0	1	0	0
0	1	1	1	1
0	1	1	0	0
1	1	1	1	1
1	1	1	0	0

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

Пример 2

Постановка условия:  Выбрать из массива нечетные положительные числа 
 
Четное число A 
Нечетное число ¬A 
Положительное число B

	Четное число	A
	Нечетное число	¬A
	Положительное число	B

 
F = ¬A Λ B  
 
Таблица истинности 
 

A	¬A	B	¬A Λ B
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0

 
Пример 3

Постановка условия: Имеем массив из N целых положительных чисел. Подсчитайте количество четных и нечетных.  
 
Если X – четное           A 
Если X – нечетное    ¬A 
 
Логическая функция F = A V ¬A 
 

A	¬A	A  V  ¬A
0	1	1
1	0	1

И что же мы имеем?      A V ¬A = 1 
 
Дизъюнкция высказывания с инверсией всегда истинна.

Рассмотрим табличную форму решения логических задач. 
 
Задача. 
 
Джуди, Айрис и Линда живут в разных городах и имеют разные профессии. Нужно определить их профессии и местожительства если известно:  
- Джуди живет не в Париже, а Линда не в Риме. 
- Парижанка не снимается в кино. 
- Та, что живет в Риме, певица. 
- Линда равнодушна к балету. 
 

Париж	Рим	Чикаго		Пение	Балет	Кино
0			Джуди			0
			Айрис			0
	0		Линда	0	0	1

Линда живет не в Риме, значит она не певица, и равнодушна к балету, значит она актриса. А Айрис и Джуди актрисами быть не могут.