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

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

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

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

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

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

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

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

аn-1 * 2n-1 +... + а1 * 21 + а0 *20 .

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

А = аn-1 аn-2 ... а1 а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.

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

X1 X2 not X1 X1 and X2 X1 or X2 X1 xor X2
False False True False False False
False True True False True True
True False False False True True
True True False True True False

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

Связь логических функций и логических операторов алгоритмического языка 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.

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

Читать еще:


Новые материалы:

Урок рефлексии. Математика. 6-й класс :: Задачи на проценты. Задачи на смеси и сплавы :: Занятие элективного курса по математике :: Семинар по теме "Теорема Пифагора" в 8-м классе :: Путешествие в мир природы (внеклассное мероприятие) :: Осколки ( Middleground ), 2017 :: Дом и дача/Текстиль/Постельное белье/Комплекты/Текстиль/Постельное белье/Комплекты Двуспальные / Karna / Комплект двуспальный ILMA ::

Отзывы (через аккаунты в социальных сетях Вконтакте, Facebook или Google+):

Оставить отзыв с помощью аккаунта ВКонтакте:

Оставить отзыв с помощью аккаунта FaceBook:

Оставить отзыв с помощью аккаунта Google+:

Поддержите сайт - подпишитесь на канал в Яндекс.Дзене!

Самое популярное:
Состояние воздуха: Карта загрязнения воздуха онлайн, обновляется в режиме реального времени

Экологическая карта состояния воздуха, которым мы дышим. В режиме реального времени.

Звуко-буквенный разбор слов

Научить детей реально оперировать звуками, т.е. развивать фонетический слух.

Урок окружающего мира на тему Когда придет суббота и когда наступит лето?

Научить детей реально оперировать звуками, т.е. развивать фонетический слух.

Тест по экономике для 10–11-х классов общеобразовательного учреждения с социально-экономическим профилем

Научить детей реально оперировать звуками, т.е. развивать фонетический слух.


Школьные занятия:
 
Контакты Научно-популярный портал "Познание - XXI век".
111672, г. Москва, ул. Новокосинская, д. 15, корп. 7.
Для связи E-mail: . poznanie21@yandex.ru
 
ADD