Алгоритм построения таблицы истинности для заданно функции имеет вид:
НАЧАЛО АЛГОРИТМА
- определение числа независимых переменных,
- определение числа рабочих строк,
- построение таблицы значений независимых переменных,
- расстановка приоритетов операций и задание их последовательности,
- построение (на бумаге) таблицы Ссылок-формул,
- ввод формул в соответствующие ячейки,
- протяжка и окончательное построение таблицы истинности для заданной функции.
КОНЕЦ АЛГОРИТМА
Согласно принципа восходящего проектирования алгоритма объединим первые три шага данного алгоритма в один подалгоритм – это задание (определение) таблицы значений независимых переменных. 4 и5 шаги объединим во второй подалгоритм, с помощью которого детализируем вычисление заданной функции. И, наконец, пункты 6 и 7 объединим в подалгоритм, завершающий построение таблицы истинности для заданной функции. В заданном алгоритме все шаги заданны функциональными блоками. Именно это позволило нам разбить его на три подалгоритма – три достаточно самостоятельных задачи.
Таким образом, наш алгоритм можно представить как линейную последовательность трех подалгоритмов, трех задач:
- для заданной функции определить и построить в электронных таблицах таблицу значений независимых переменных,
- построить таблицу ссылок-функций,
- построить таблицу истинности для заданной функции.
Рассмотрим первую из них.
ЗАДАЧА №1. Построить в электронных таблицах таблицу значений независимых переменных для заданной логической функции.
Данная задача, по своему определению, требует:
- определения числа независимых переменных (в заданной функции),
- вычисления числа рабочих строк,
- построения таблицы значений независимых переменных.
Переменные в логике обозначаются (каждая переменная) одной латинской буквой. Поэтому, для определения числа независимых переменных необходимо посчитать количество использованных в заданной функции латинских букв.
Зададим таблицу ввода стандартно.
№ строки/адрес столбца | A | B |
1 | комментарии | значения |
2 | N | 5 |
3 | M | =<формула> |
Здесь N – число независимых переменных,
М – максимальный номер рабочих строк.
B3 =>[=2^b2-1] – читаем – “в ячейку b3 вводится формула, заключенная в прямоугольные скобки”.
Для решения нашей задачи предложим следующую модель...
Если номер строки – десятичное число представить в двоичном виде, а значение каждого разряда записать отдельную ячейку, то для данной строки мы получим набор значений независимых переменных. Если это проделать для всех рабочих строк, то мы получим набор значений независимых переменных. А так как номера строк изменяются от 0 до максимального значения, то набор будет полным.
Для решения этой задачи необходимо
A8=>[<разряды>]-(комментарии)
B8=>[=b2]
C8=>[=Если(И(b8<b2;b8>0);b8-1;””)]
C8->H8 – последнее читается как “формула, введенная в ячейку С8, копируется до ячейки Н8 включительно”. Для задания номеров рабочих строк необходимо ввести:
a10=[0]
a11=> [= Если(и($a10<$b$3;$a10<0);a10+1;””)]
a11->a50, то есть формула из а11 копируется в ячейки до а50.
И, наконец, вводим
b10=>[=Если(и($a10>0;b$8>0);Остат(Целое($a10/2^b$8);2);””)]
b10->h50
Таким образом, получаем таблицу значений независимых переменных, настроенную для N<=5. Изменения значения в ячейке b2 (должно быть в пределах от2 до5) что приводит к автоматической перестройке таблицы
Пример полученной таблицы приведен ниже.на Рис. №1.
Рис. 1
ЗАДАЧА РЕШЕНА
Сформулируем следующую задачу.
ЗАДАЧА №2. Построить таблицу ссылок-формул.
Решим данную задачу на следующем примере. Пусть задана следующая функция
F = AB+C->¬D?¬(A+B)
Согласно алгоритма, на первом шаге мы определяем, что в исходной функции имеем четыре независимых переменных (N=4) По полученному N определяем значение М.
Далее, расставить приоритеты операций, это определить последовательность операций для вычисления данной функции.
В логике заданы следующие приоритеты:
(...), ¬ , V, +, ->, ? далее операции сравнения.
Согласно данного расставляем последовательность операций в нашей функции
Составим таблицу ссылок – формул
№операции | операция | операнды | Куда(адрес) | ЧТО(формула) |
1 | 2 | 3 | 4 | 5 |
1 | A+B | b10,c10 | F10 | =Если(b10+C10>0;1;0) |
2 | Not[1] | f10 | G10 | =Если(f10>0;0;1) |
3 | Not D | e10 | H10 | =Если(e10>0;0;1) |
4 | AB | b10,c10 | I10 | =Если(b10Vc10>0;1;0) |
5 | [4]+C | I10, d10 | J10 | =Если(i10+d10>0;1;0) |
6 | [5]->[3] | J10,h10 | K10 | =Если(j10>h10;0;1) |
7 | [6?[1] | K10,f10 | L10 | =Если(k10=f10;1;0) |
Все наглядно, все проверяемо.
ЗАДАЧА РЕШЕНА.
Нам остается в ячейки, указанные в столбце №4, ввести формулы, записанные в столбце №5, и перекопировать формулы из ячеек с введенными формулами в строке №10 в заданных столбцах от F до L до последней рабочей строки. В столбце L будем иметь значения заданной функции.
Исходная задача решена.
Следует отметить, что данная технология допустима в EXCEL офисов 97/2003,где позволяет определять таблицы истинности для не более 16 независимых переменных и не более 120 операций в заданной функции. Этого вполне достаточно как для средней школы, так и для учебного процесса в высших учебных заведениях для соответствующих специальностей. (EXCEL 2010 допускает большие возможности как по числу независимых переменных, так и по числу операций в заданной функции.