Информатика. 10 класс

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

Конспект урока

Информатика, 10 класс. Урок № 12.

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

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

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

http://lbz.ru/metodist/authors/informatika/3/eor10.php

http://kpolyakov.spb.ru/school/ege.htm

Теоретический материал для самостоятельного изучения.

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

Основные законы алгебры логики

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

Последовательно применим дистрибутивный закон и закон исключенного третьего:

В общем случае можно предложить следующую последовательность действий:

  1. Заменить операции строгая дизъюнкция, импликация, эквиваленция на их выражения через операции конъюнкция, дизъюнкция, инверсия;
  2. Раскрыть отрицания сложных выражений по законам де Моргана.
  3. Используя законы алгебры логики, упростить выражение.

Пример 2. Упростим логическое выражение .

Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.

Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:

Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат становился истинным высказыванием при любых значениях x.

Преобразуем исходное выражение, избавившись от импликации:

A, B, C — множества. Для них можно записать (U — универсальное множество).

Будем считать, что.

Тогда , причем это минимально возможное множество А.

Так как множество B — это отрезок [2;12], а множество — это промежутки и, то пересечением этих множеств будет служить промежуток . В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

Введем обозначения:

Перепишем исходное выражение в наших обозначениях и преобразуем его:

Рассмотрим предикат . В числе 2810=111002 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 4510=1011012 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 1710=100012 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы .

Запишем это выражение для рассмотренных множеств истинности:

Так как , примем .

Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: , и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 1011002 = 4410.

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

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

Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.

A

B

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

F1(A,B) = 0 — константа «ложь»;

F2(A,B) = A&B — конъюнкция;

F3(A,B) = — отрицание импликации;

F4(A,B) = A — функция, равная первому аргументу;

F5(A,B) = — отрицание обратной импликации;

F6(A,B) = B — функция, равная второму аргументу;

F7(A,B) = — строгая дизъюнкция;

F8(A,B) = A˅B — дизъюнкция;

F9(A,B) = — стрелка Пирса (отрицание дизъюнкции, ИЛИ-НЕ);

F10(A,B) = — эквиваленция;

F11(A,B) = — отрицание второго аргумента;

F12(A,B) = — обратная импликация;

F13(A,B) = — отрицание первого аргумента;

F14(A,B) = — импликация;

F15(A,B) = — штрих Шеффера (отрицание конъюнкции, И-НЕ);

F16(A,B) = 1 — константа «истина».

С увеличением числа аргументов количество логических функций резко возрастает. Отметим, что путем преобразований функция любого количества переменных может быть выражена через функции только двух переменных. Более того, можно использовать не все, а лишь некоторые логические функции двух переменных. Например:

  1. F2 и F11 (конъюнкция и отрицание второго аргумента);
  2. F8 и F13 (дизъюнкция и отрицание первого аргумента);
  3. F9 (стрелка Пирса, отрицание дизъюнкции);
  4. F15 (штрих Шеффера, отрицание конъюнкции).

Последние два примера говорят о том, что при желании всю алгебру логики можно свести к одной функции.

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

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

При решении задач часто требуется по таблице истинности логической формулы записать ее аналитическое выражение. Для этого используются понятия совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).

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

Аналогично, выражение простая дизъюнкция.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение является ДНФ.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. Например, выражение является КНФ.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные (либо сами, либо их отрицания). Например, выражение является ДНФ, но не СДНФ. Выражение же представляет собой СДНФ.

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

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

  1. Отметить в таблице истинности наборы переменных, при которых значение логического выражения равно единице;
  2. Для каждого отмеченного набора записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — её отрицание;
  3. Все полученные конъюнкции связать операциями дизъюнкции.

Пример 5. Имеется следующая таблица истинности:

После выполнения первых двух шагов алгоритма получим:

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

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

Предметы

По алфавиту По предметным областям

Классы

1 2 3 4 5 6 7 8 9 10 11
angle-skew-bottom mix-copy next-copy-2 no-copy step-1 step-2 step-3 step-4 step-5 step-6 step-6