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

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

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

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

Читать еще:


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

Урок математики в 1-м классе по теме "Закрепление таблицы сложения и вычитания в пределах 20" :: Национально-региональный компонент как средство воспитания экологической культуры младших школьников (из опыта работы) :: Урок экономики "Кубань — житница России", 4-й класс :: Формирование полноценного навыка чтения у младших школьников :: Урок окружающего мира по теме "Красная книга" :: Одарённая ( Gifted ), 2017 :: Дом и дача/Текстиль/Постельное белье/Комплекты/Текстиль/Текстиль для детской/Комплекты постельного белья/Комплекты в кроватку / HOBBY Home Collection / Комплект детский PONPON ::

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

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

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

Самое популярное:
Звуко-буквенный разбор слов : Начальная школа - Хелси и Смарт

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

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

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

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

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

Год свиньи 2019 - чем он характеризуется и что несет : новый год - Хелси и Смарт

Свинья всегда стояла в животном мире особняком. Решая сходные с человеческими задачи, построив на совершенно иной генетике организм настолько близкий к человеческому, что хоть сейчас сердце пересаживай (об этом чуть ниже), свинья остается одинаково свободной в любой обстановке - хоть в грязной луже, хоть на дворцовом паркете.

Лабораторная работа №3 "Знакомство с внешним строением растения". 5-й класс : Биология

Урок биологии в 5-м классе по программе Понаморевой И.П. является 2-м в теме «Растения». Тип урока: урок комплексного применения знаний с целью продолжить формирование представления об органах растений: вегетативных и генеративных; значении их для растения; развитие понятий “орган”, «голосеменные», «покрытосеменные» «вегетативные органы» «генеративные органы» формирование представлений о двух группах органов, вегетативных (побег и корень) и генеративных (цветок, плод с семенами).

Контроль знаний учащихся 10-го класса по темам "Алкены"и "Алкины" : Химия - Хелси и Смарт

Данная работа предложена учащимся с целью контроля усвоения программного материала по непредельным углеводородам (алкинам и алкенам) и задачами: проверить уровень усвоения номенклатуры и изомерии, умение получать алкены и алкины, составлять уравнения реакций с их участием, решать качественные и расчетные задачи по данным темам. Работа составлена с учетом индивидуального подхода: 1 вариант - облегченный; 2 вариант - средний уровень; 3 вариант - усложненный.

Тестовые задания по экологии : Экология

Тестовые задания предназначены для проверки и закрепления знаний учащихся 8–11-х классов по курсу «Основы экологии». Данные тесты дают возможность быстро и объективно организовать проверку знаний учащихся по разделам «Основы экологии», «Учение о биосфере», «Экология популяций», «Взаимоотношения организмов», «Экология экосистем».


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