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

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

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

Оборудование и программное обеспечение: компьютеры, интегрированная система 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.

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

Читать еще:


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

Урок информатики в 5-м классе по теме "Процессор. Внутренняя и внешняя память компьютера. Организация хранения информации" :: Урок информатики по теме "Циклы с предусловием и постусловием" :: Предпрофильный курс по выбору "Социальные сервисы Web2.0" :: Информационные процессы :: Воспитание толерантности :: Орбита 9 ( Órbita 9 ), 2017 :: Дом и дача/Мебель/Столы и стулья/Компьютерные столы/Столы/Для комнат/Компьютерные столы / Ная ТД / Компьютерный стол Ная ТД ::

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

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

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

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

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

Самое популярное:
Звуко-буквенный разбор слов

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

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

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

Тесты для задания 7 ЕГЭ по русскому языку

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

Водоемы Краснодарского края. Их использование и их охрана

Урок дает возможность сформировать представления учащихся о водоемах нашего края.

Урок по фольклору (предмет по выбору). Тема: "Хлеб на стол и стол - престол

Урок дает возможность сформировать представления учащихся о водоемах нашего края.

Урок истории в 5-м классе по теме "Жизнь египетского вельможи"

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

Задания для проведения школьной олимпиады по химии для учащихся 8–10-х классов

В работе представлены задачи для проведения школьного тура олимпиады по химии для обучающихся 8–10-х классов. Олимпиада может включать заочный и очный туры. Задания должны быть разнообразными по содержанию и типу. Уровень сложности заданий должен быть доступен для большинства школьников, но по своей форме задания должны отличаться от контрольной работы по химии необычностью постановки вопроса, а в ответах на них должны допускаться приемы решений, которые не являются стандартными.

Девятая жизнь Луи Дракса (The 9th Life of Louis Drax, Великобритания, 2016) - спойлеры, пересказ, трактовка

Этот фильм заслуживает растаскивания на цитаты. "С возрастом я сам научился понимать, чего от меня хотят", "Мужчины всегда думают, что раз она красивая - значит, она хорошая" - и много другого. Вообще очень достоверный фильм в отношении психологических деталей. Рекомендую к просмотру.


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