Два урока математической логики с использованием электронных таблиц EXCEL

Разделы: Информатика


Для огромного числа задач математической логики требуется определение таблицы истинности заданной логической функции. Данная задача решается, как правило, вручную. Но это хорошо для двух – трех независимых логических переменных. А если таких переменных пять или более? Рассмотрим возможности EXCEL для решения подобных задач.

УРОК № 1

Для первого урока выделим следующие две подзадачи:

  • построения таблицы комбинаций значений независимых переменных,
  • построения таблиц истинности базовых логических операций.

Для формулировки первой подзадачи рассмотрим таблицу №1, в которой приведены все возможные комбинации значений для трех независимых логических переменных.

ТАБЛИЦА №1

A

B

C

0

0

0

0

1

0

0

1

2

0

1

0

3

0

1

1

4

1

0

0

5

1

0

1

6

1

1

0

7

1

1

1

Из таблицы №1 видно, что для каждой строки числа в столбцах “А”, “В”, “С” можно рассматривать как цифры двоичного представления десятичного числа, значение которого введено в соответствующей строке столбца “№”. Это позволяет поставить следующую задачу.

ЗАДАЧА № 1. Для интервала целых десятичных чисел А(10) I [0, 2^N-1], где N – число независимых логических переменных, получить цифры их двоичного представления, при этом в одном столбце записывается цифра одного и того же разряда (Полученную таблицу можно рассматривать как таблицу всех возможных комбинаций значений независимых переменных – здесь столбец соответствует одной из независимых переменных).

РЕШЕНИЕ

НА ВЫХОДЕ таблица значений логических переменных.

НА ВХОДЕ N – число независимых переменных. Конкретно, пусть N=4.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ.

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

A (2) => a0*2^0 + a1*2^1 + a2*2^2 + …+ an*2^n => A (10) (1)

Здесь a0, a1,…,an – двоичные цифры исходного двоичного числа A(2).

A(10) – его десятичное представление, если вычислить арифметическое выражение, заключенное между двумя знаками равенства.

Следовательно, заданное десятичное число А(10) можно представить в развернутом виде с двоичной базой.

A (10) = a0*2^0 + a1*2^1 + a2*2^2 + …+ an*2^n (2)

Нашей задачей является определение значений a0, a1,…,an. Это задача  целочисленной арифметики.

Для определения значения ai (где i –разряд цифры) можно воспользоваться формулой:

ai = ОСТАТОК (ЦЕЛОЕ (A (10)/2^i);2)

здесь i – разряд данной цифры в двоичном представлении исходного десятичного числа А (10).

Обоснование этой формулы дано в приложении №1, его можно задать как домашнее задание ученикам.

<РИСУНОК 1>

Ученикам можно дать задание: обосновать применение во вводимой формуле именно этих ссылок.

МОДИФИКАЦИЯ данной таблицы необходима, если число независимых переменных отлично от 4.

Задания для работы как в классе, так и дома:

  1. разработать алгоритмы модификации полученной таблицы для числа независимых переменных больше 4 и меньше 4,
  2. решить задачу проверки полученной таблицы (например, в ячейке А3 при хотя бы одной неверной строки пусть выводится слово “ОШИБКА”, а если все правильно, то ничего не выводится).

ЗАДАЧА РЕШЕНА

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

ЗАДАЧА № 2. Построить таблицы истинности для базовых логических операций.

РЕШЕНИЕ

ЗАМЕЧАНИЕ. Ограничимся логическими операциями традиционно рассматриваемыми в школьной программе: логические отрицание, умножение и сложение, импликация и эквивалентность.

НА ВЫХОДЕ необходимо получить пять таблиц истинности пяти логических операций.

НА ВХОДЕ определения логических операций.

Для решения поставленной задачи нет необходимости в таблице ввода/вывода. Для каждой логической операции таблица истинности определяется самостоятельно и независимо от других, то есть мы фактически имеем пять самостоятельных задач. А так как только одна операция “НЕ” работает с одной переменной, а все остальные с двумя, то есть смысл унарную операцию логического отрицания вывести в одну таблицу, а все остальные бинарные операции объединить в одну таблицу.

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

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ.

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

  • логическое отрицание – если A>0, то 0, иначе 1,
  • логическое умножение – если A*B=1, то 1, иначе 0,
  • логическое сложение – если A+B>0, то 1, иначе 0,
  • импликация – если A>B, то 0, иначе 1,
  • эквивалентность – если A=B, то 1, иначе 0.

Здесь А, В – независимые логические переменные.

Следует подчеркнуть, что в данных определениях мы используем логические значения переменных 1 (истина) и 0 (ложь), то есть, логические значения “ИСТИНА” и “ЛОЖЬ” обозначаются числами 1 и 0. Именно поэтому, определения логических операций записаны в арифметическом виде.

В результате получаем следующие таблицы.

<РИСУНОК 2>

ЗАДАЧА РЕШЕНА

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

Умея решать эти подзадачи, можно по заданному алгоритму построить таблицу истинности любой логической функции, не включающей в себя логические функции, выходящие за указанные выше (“И”, “ИЛИ”, “НЕ”, “ИМПЛИКАЦИЯ”, “ЭКВИВАЛЕНТНОСТЬ”).

УРОК № 2

На данном уроке рассмотрим особенности построения таблиц истинности заданной логической функции.

В общем виде алгоритм построения таблицы истинности любой логической функции следующий:

  1. определяем количество независимых переменных, число которых определяет полное количество независимых комбинаций значений независимых логических переменных 2^N (здесь N – число независимых переменных);
  2. построить таблицу комбинаций значений независимых переменных,
  3. по заданной формуле определяем последовательность базовых операций,
  4. строим вспомогательную таблицу (таблицу ссылок – формул),
  5. вводим формулы базовых операций в требуемой последовательности в расчетную таблицу.

ЗАДАЧА №3. Построить таблицу истинности следующей логической функции F = A* not(B) + C D -> E.

РЕШЕНИЕ ЗАДАЧИ

Решим данную задачу по приведенному выше алгоритму.

1.

Исходная функция F зависит от пяти независимых логических переменных, то есть N=5. Следовательно, число комбинаций значений независимых переменных для заданной функции будет равной M = 2^N =32.

2.

Построенная в задаче №1 предыдущего урока таблица комбинаций значений независимых логических переменных требует модификации. Для этого необходимо:

  • между столбцами А и В вставить новый столбец,
  • в ячейку В2 ввести 4,
  • в столбец В, начиная с В5 скопировать из столбца С формулу,
  • замаркировать стоки 19 и 20 и протянуть до строки №36.

Проверку и обоснование данной модификации можно предоставить ученикам.

Результат решения данной подзадачи приведен в ТАБЛИЦЕ №4.

3.

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

4.

Строим вспомогательную таблицу в рабочих тетрадях (на бумаге) в виде:

№ операции

ОПЕРАЦИЯ

Cсылки, используемые в операциях

ФОРМУЛА

Куда вводить

[1]

[2]

[3]

[4]

[5]

1

not B

С5

=ЕСЛИ (С5>0;0;1)

G5

2

A*(not B)

B5, G5

=ЕСЛИ(B5*G5=1;1;0)

H5

3

(A*not B)+C

H5, D5

=ЕСЛИ(H5+D5>0;1;0)

I5

4

D -> E

E5, F5

=ЕСЛИ(E5>F5;0;1)

J5

5

(A*notB+C)=

(D->E)

I5, J5

=ЕСЛИ (I5=J5; 1; 0)

K5

ЗАМЕЧАНИЯ:

  • В ТАБЛИЦЕ № 2 в круглые скобки заключается блок уже выполненных операций. Более удобно, но менее наглядно, в круглых скобках указывать номера последних операций блока, это можно делать после разработки и построения десятка – двух десятков таблиц истинности разных функций.
  • Таблицы истинности этих логических операций получены в задаче №2 предыдущего урока.

5.

Для построения таблицы истинности заданной функции в расчетной таблице в ячейки, указанные в колонке №5 ТАБЛИЦЫ № 2 ввести соответствующие формулы, записанные в этой же таблице в колонке №4. Далее маркируем формулы и протягиваем (копируем) по столбцу на все рабочие строки (в данном случае на 31 строку).

В итоге получаем решение данной задачи.

<РИСУНОК 3>

ЗАДАЧА РЕШЕНА

Для контроля работы учащихся можно для каждой таблицы получить суммы по строкам и столбцам рабочего поля таблицы (в нашем примере – [G5:K36], и сопоставить эти числа для всех.

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