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

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

Оборудование и программное обеспечение: компьютеры, интегрированная система Turbo Pascal, файл с текстом программы вычисления корней системы логических уравнений на алгоритмическом языке Pascal. Раздаточный материал: “Операции отношения и логические операции в Pascal”, “Таблицы истинности логических операций”, текст программы вычисления корней системы логических уравнений, варианты систем логических уравнений, варианты логических выражений.

Логическое выражение – конструкция, состоящая из данных, операций отношения, логических операций, арифметических выражений. Логическое выражение имеет два значения: True (истина) или False (ложь). Логическое уравнение - уравнение вида F(x1,x2,...,xn) = Q, где F- булева функция n переменных, Q имеет значение true или false.Такое уравнение может иметь от 0 до 2ⁿ различных решений. Несколько уравнений относительно одних и тех же неизвестных образуют систему уравнений. Решением системы Z уравнений будет набор значений x1,x2,...,xn, обращающих все уравнения в тождества после подстановки их вместо соответствующих неизвестных, то есть набор, на котором истинна логическая функция W, являющаяся конъюнкцией исходных функций F, W=F1 ? F2 ? ...FZ. Такая функция может быть задана таблицей истинности, содержащей 2ⁿ наборов переменных. Таблица истинности – таблица, в которой указаны значения логической функции для всех возможных комбинаций значений ее аргументов.

Решение системы логических уравнений посредством построения таблиц истинности можно получить с помощью простой компьютерной программы. Такая программа должна генерировать все переборы из n элементов и вычислять значение W функции на этих наборах, выводить возможные комбинации переменных, являющихся решениями системы логических уравнений. Известны эффективные комбинаторные алгоритмы, позволяющие создавать множество наборов из n нулей и единиц. Тогда в каждом наборе нулю будет соответствовать значение логической переменной равной false, а единице – true. Ограничимся простыми алгоритмами перебора 0-1 вектора, основанными на двоичном представлении чисел. Эти алгоритмы позволят повторить на занятии изученные ранее темы, связанные с переводом чисел из десятичной системы счисления в двоичную систему и арифметическими операциями над двоичными числами.

Рассмотрим алгоритм, основанный на сложении двоичных чисел. Существует взаимно однозначное соответствие между числами из 0...2ⁿ – 1 и наборами 0-1 векторов. Достаточно первым взять число 0 в двоичном представлении, а затем прибавлять двоичную единицу, тогда на каждом текущем наборе будем иметь последовательность нулей и единиц, представляющую двоичное число, последним набором будет набор из одних единиц.

Второй алгоритм работает на основе перевода целого десятичного числа в двоичную систему счисления методом деления. Число A можно представить как

а_n-1 * 2^n-1 +... + а₁ * 2¹ + а₀ *2⁰ .

Разделим A на 2, тогда неполное частное будет а_n-1 * 2^n-1 + ... +а₁ , остаток а₀, полученное неполное частное опять разделим на 2, остаток от деления будет а₁ и т.д. пока частное не будет меньше 2. На последнем шаге получим набор остатков а₀, а₁, а₂, ..., а_n-1, которые входят в двоичное представление числа A и совпадают с остатками от последовательного деления данного числа на 2. Соберем остатки в обратном порядке.

А = а_n-1 а_n-2 ... а₁ а_0. Для получения перебора 0-1 вектора поочередно, начиная с 0, переводим десятичные числа в двоичную систему счисления. Этот алгоритм реализован в программе.

Предоставляемую программу можно считать программой с открытым исходным кодом. Исходный код таких программ сам может служить документацией, так как он доступен для просмотра, изучения и изменения, что позволяет пользователю принять участие в доработке самой программы, использовать код для создания новых программ и исправления в них ошибок, изучать используемые алгоритмы. В программе практически отсутствует интерфейс по вводу данных, так как учащиеся работают с текстом программы, и их основной задачей является составление и запись логической функции в тело функции (function xlog:Boolean). Неизвестными уравнений и операндами логических выражений являются элементы массива Х, то есть Х[1], Х[2],..., Х[n], где n – число переменных.

Текст программы

Комментарии по тексту программы поясняют основные моменты работы.

Program Logist;{Вычисление корней системы логических уравнений}

Const

nn=100;{максимальное число неизвестных}

var a,b,c,i,j,k,m,n,ii,resh:integer;

mas: array[0..nn-1] of byte;{комбинация нулей и единиц}

x:array[1..nn] of boolean;{строка таблицы истинности}

xlog:boolean;

{Запись системы уравнений, x[1],x[2] и т.д.- неизвестные}

function xlog:boolean;

begin

{логическую функция программирует учащийся}

{ xlog:= (уравнение 1) and (уравнение 2) and ... (уравнение n);}

end;

begin

k:=0;

writeln('число переменных ');

readln(n);{n-число переменных}

m:=1;

for i:=1 to n do m:=m*2;{вычисление числа строк таблицы истинности}

m:=m-1;

for j:=0 to m do {перебор десятичных чисел}

begin

a:=j;

repeat

b:=a mod 2;

mas[k]:=b;{запись остатков от деления}

c:=a div 2;

if c>=2 then a:=c;

k:=k+1;

until c<2;

mas[k]:=c;

for ii:=1 to nn+1 do x[ii]:=false;

for i:=n-1 downto 0 do {формирование строки таблицы истинности}

begin

ii:=n-i;

if mas[i]=1 then x[ii]:=true else x[ii]:=false;

end;

if xlog=true then {вывод результатов}

begin

for k := 1 to n do write ('x',k,'=',x[k],', ');

resh:=resh+1;{подсчет числа решений}

end;

writeln;

for i:=0 to nn do mas[i]:=0;

k:=0;

end;

writeln('число решений = ',resh);

end.

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

Операции отношения в языке Pascal: равно (=), не равно (<>), меньше (<), меньше либо равно (<=), больше (>), больше либо равно(>=).

Логические операции в порядке приоритетов: NOT, AND, OR, XOR.

"Таблицы истинности" результатов логических операций:

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

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

Этапы работы:

1. Подготовка компьютера к работе, загрузка файла шаблона программы.

2. Изучение методов генерации таблицы истинности, алгоритма работы программы, и их реализации на алгоритмическом языке.

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

4. Запись логических уравнений и решение системы уравнений.

5. Упрощение логических выражений и проверка их равнозначности.

1. Решение систем логических уравнений. Пусть задана система уравнений:

Неизвестных 8. Необходимо составить логическое выражение, объединяющая эти уравнения . Тогда логическая функция (function xlog:boolean), записанная на языке Pascal, будет иметь следующий вид:

xlog:=((not x[1] or x[2]) and (not x[2] or x[3]) and (not x[3] or x[4]) = true) and((not x[5] or x[6]) and (not x[6] or x[7]) and (not x[7] or x[8]) = true ) and((not x[5] or x[1]) and (not x[6] or x[2]) and ( not x[7] or x[3]) and( not x[8] or x[4]) = true )

Результаты работы программы:

х1= false, х2= false, х3=false, х4= false, х5= false , х6=false, х7= false, х8= false;

х1= false, х2= false, х3=false, х4= true , х5= false , х6=false, х7= false, х8= false;

х1= false, х2= false, х3=false, х4= true , х5= false , х6=false, х7= false, х8= true;

х1= false, х2= false, х3= true, х4= true , х5= false , х6=false, х7= false, х8= false;

х1= false, х2= false, х3= true, х4= true, х5= false , х6=false, х7= false, х8= true;

х1= false, х2= false, х3= true, х4= true , х5= false , х6=false, х7= true, х8= true;

х1= false, х2= true, х3= true, х4= true , х5= false , х6=false, х7= false, х8= false;

х1= false, х2= true, х3= true, х4= true , х5= false , х6=false, х7= false, х8= true;

х1= false, х2= true, х3= true, х4= true , х5= false , х6=false, х7= true, х8= true;

х1= false, х2= true, х3= true, х4= true , х5= false , х6= true, х7= true, х8= true;

х1= true, х2= true, х3= true, х4= true , х5= false , х6=false, х7= false, х8= false;

х1= true, х2= true, х3= true, х4= true , х5= false , х6=false, х7= false, х8= true;

х1= true, х2= true, х3= true, х4= true , х5= false , х6=false, х7= true, х8= true;

х1= true, х2= true, х3= true, х4= true , х5= false , х6= true, х7= true, х8= true;

х1= true, х2= true, х3= true, х4= true , х5= true , х6= true, х7= true, х8= true;

Число решений=15.

2. Проверка правильности упрощения логического выражения. Программа может быть использована для проверки правильности упрощения логического выражения. Пусть исходное выражение

. После упрощения получили .

Тогда объединяющая функция W = f1 f2. Логическая функция в тексте программы (function xlog:boolean) будет иметь следующий вид.

xlog:= ((x[1] or x[2]) and (not x[1] or x[2]) and (not x[1] or not x[2])) = (x[2] and not x[1]).

Число логических операндов 2, тогда количество строк в таблице истинности равно 4. Если эти функции тождественны, тогда число решений должно быть тоже 4.

Результаты работы программы:

x1=false, x2= false;

x1=false, x2= true;

x1=true, x2= false;

x1=true, x2= true.

Число решений=4.

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