Для огромного числа задач математической логики требуется определение таблицы истинности заданной логической функции. Данная задача решается, как правило, вручную. Но это хорошо для двух – трех независимых логических переменных. А если таких переменных пять или более? Рассмотрим возможности 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, его можно задать как домашнее задание ученикам.
Ученикам можно дать задание: обосновать применение во вводимой формуле именно этих ссылок.
МОДИФИКАЦИЯ данной таблицы необходима, если число независимых переменных отлично от 4.
Задания для работы как в классе, так и дома:
- разработать алгоритмы модификации полученной таблицы для числа независимых переменных больше 4 и меньше 4,
- решить задачу проверки полученной таблицы (например, в ячейке А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^N (здесь N – число независимых переменных);
- построить таблицу комбинаций значений независимых переменных,
- по заданной формуле определяем последовательность базовых операций,
- строим вспомогательную таблицу (таблицу ссылок – формул),
- вводим формулы базовых операций в требуемой последовательности в расчетную таблицу.
ЗАДАЧА №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 строку).
В итоге получаем решение данной задачи.
ЗАДАЧА РЕШЕНА
Для контроля работы учащихся можно для каждой таблицы получить суммы по строкам и столбцам рабочего поля таблицы (в нашем примере – [G5:K36], и сопоставить эти числа для всех.
Важно отметить, что данный подход практически не ставит ограничений на количество независимых переменных в исходной формуле логики, для которой и строится таблица истинности.