Преобразование логических выражений

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

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

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

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

4)

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

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

6) (выносятся за скобки общие множители; применяется правило операций с константами);

7)

(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);

8)

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

9)

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

10)

(используются правило де Моргана, закон двойного отрицания и закон поглощения).

Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.

Циклические вычислительные процессы.

Даны массивы A_i , i=1,…,10 и B_j , j=1,…,15. Найти максимальные элементы массивов A_min и B_min. Определить, какой из A_min или B_min больше по абсолютной величине.

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

Решение

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

.

Перед началом цикла задается начальное значение A_min=A₁, и поиск в цикле начинается со второго элемента.

Аналогично вычисляется и B_min.

Схема будет содержать два цикла: первый по параметру i от 2 до 10 с шагом 1, второй по параметру j от 2 до 15 с шагом 1. В результате работы первого цикла будет вычислен A_min, в результате работы второго - B_min. Схема вычислений приведена на рис. 11.

Рис. 28. Схема вычисления A_min , B_min и анализ их значений по абсолютной величине.

Исходные данные – массивы A_i , i=1,…,10. и B_j , j=1,…,15 состоят из переменных вещественного тип, значения которых зададим самостоятельно. Первым оператором программы будет оператор DIMENSION, который объявит массивы и укажет их максимальный размер.

Для ввода исходных данных (общее количество элементов массивов равно 25) используем невыполняемый оператор DATA. Результаты выведем на дисплей под управлением списка.

Циклы организуем с помощью структурного оператора цикла. Для выбора минимальных элементов внутри циклов Amin и Bmin и сравнения их по абсолютной величине используем логический оператор IF.

Как и в примере 2 для “читаемости” снабдим программу комментариями.

Текст программы на алгоритмическом языке Basic. Массивы A и B определены явно и имеют тип Single (действительные числа с обычной точностью). Остальные переменные имеют тип Variant. Ввод данных в массивы А и В осуществляется в использование оператора DATA непосредственно из программы. Вывод производится на экран дисплея осуществляется под управлением списка.

‘ Вычисление количества положительных элементов в массивах

DIM A(10) as Single, B(15) as Single

‘ Ввод массивов

DATA -20.42,-11.80,-19.90, 44.86, 47.98,-9.86,-22.17,-33.96,-33.72,

14.66,-8.99,-8.72,21.27,-17.38,13.32,-29.24,-31.40,8.34,-41.93,

-4.20,40.57,-23.86, 28.52,-12.11,-21.03

FOR I = 1 TO 10

READ A(I)

NEXT I

FOR J = 1 TO 15

READ B(J)

NEXT J

‘ Задание начальных значений

Amin = A(1)

Bmin = B(1)

‘ Организация цикла по параметру I. Выбор Amin

FOR I = 2 TO 10

‘ Выбор минимального элементов массива A и сохранение в Amin

IF(A(I) < Amin )THEN

Amin = A(I)

ENDIF

NEXT I

‘ Организация цикла по параметру J. Выбор Bmin

FOR J = 2 TO 15

‘ Выбор минимального элементов массива B и сохранение в Bmin

IF(B(J) < Bmin)THEN

Bmin = B(J)

ENDIF

NEXT J

‘ Печать Amin и Bmin

PRINT ’ Amin=’,Amin,’ Bmin=’,Bmin

‘ Сравнение |Amin| и |Bmin|

IF(ABS(Amin) > = ABS(Bmin))THEN

PRINT ’ |Amin| больше или равен |Вmin|’

ELSE

PRINT ’ |Bmin| больше |Amin|’

ENDIF

END

Приложение 1