Примеры выполнения заданий. 1.Докажите: x & Ú º ;

1.Докажите: x & Ú º ;

1) x & Ú º x & Ú & (по закону де Моргана);

2) x & Ú & º & (x Ú ) (по дистрибутивному закону);

3) & (x Ú ) º & И (по закону исключения третьего);

4) & И º (по свойству логической константы И).

2. Упростите: x & (y → x) → º

1) x & (y → x) → º x & ( Ú x) → (по равносильности);

2) x & ( Ú x) → º Ú (по равносильности);

3) Ú º Ú ( & ) Ú (по закону де Моргана);

4) Ú ( & )Ú º Ú (y& )Ú (по закону снятия дв.отрицания);

5) Ú (y & ) Ú º Ú (по закону поглощения).

3.Определите тождественную истинность или ложность формулы

X & Y & →Y º

1) X & Y & →Y º Ú Y (по равносильности)

2) Ú Y º Ú Ú Ú Y (по закону де Моргана)

3) Ú Ú Ú Y º Ú Ú X Ú Y (по закону снятия дв.отрицания);

4) Ú Ú X Ú Y º Ú XÚ Ú Y (по коммутативному закону);

5) Ú XÚ Ú Y º И Ú И º И (по закону исключения третьего).

Задания для самостоятельного выполнения

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

0) Если усложнить схему устройства, то возрастает его производительность, а если использовать новую элементную базу, то увеличится период эксплуатации. Устройство начнут хорошо раскупать только при одновременном росте его производительности и периода эксплуатации. Но устройство не пользуется спросом.

1) Увеличение денег в обращении влечёт за собой инфляцию. Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота. Снижение товарооборота приводит к безработице и спаду производства. Из-за инфляции падает курс денежной единицы. Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство, тогда избежим безработицы, и курс денежной единицы останется неизменным.

2) Любой марксист-диалектик, но не всякий диалектик-марксист. Любой марксист-материалист, но не всякий материалист-марксист. Гегель был диалектик, но не материалист. Фейербах был материалист, но не диалектик. Итак, если бы Гегель и Фейербах могли объединиться в один кружок, то Маркс уже не понадобился бы.

3) Существуют две теории возникновения человека на земле - теория эволюции Дарвина и теория сотворения человека Господом Богом. Если справедлива теория эволюции, то самопроизвольное возникновение человека без соответствующих превращений живых организмов невозможно. Как доказали учёные, такие превращения действительно имели место. По теории же сотворения человек был слеплен из простой глины, а жизнь в него вдохнул господь. Глины всегда было много, а на счёт дыхания Бога тоже сомневаться не приходиться, поскольку есть на то свидетельство Библии. Отсюда вывод – две названные теории друг другу не противоречат.

4) Из утверждения ”два плюс два равно пяти” следует, что я и папа римский - одно и то же лицо. В самом деле, если от обеих частей указанного равенства отнять по двойке, то будет справедливо равенство ”два равно трём”. Если от обеих частей нового равенства отнять по единице, то будет справедливо равенство - “один равен двум”. Один - это я, а двойка - это я и папа римский. Поскольку верно, что ”один равен двум”, то я есть папа римский.

5) Сегодня посмотрю футбол, если трамвай не задержится. Трамвай не опоздал, но случилась другая беда: у меня не оказалось денег на билет. Рискну доехать «зайцем». В салоне оказался контролер, и я лихорадочно стал рыться по карманам. К моему счастью, нашелся один неиспользованный трамвайный талон. До компостера я добрался вовремя, хотя футбольный матч я так и не увидел: вместе с деньгами я дома оставил и билет на матч.

6) Если в оном месте что-то убудет, то в другом месте что-то прибудет – это истина, не требующая доказательства. Но есть такая теория, которая утверждает: где-то в далеком космосе существуют «черные дыры», куда все проваливается, но оттуда ничего не появляется. Эта теория ничего не говорит о существовании «белых дыр», которые действовали бы противоположно «черным». Один иностранный астрономический журнал сообщил координаты «черной дыры». Российский астроном Иванов направил туда мощный телескоп и ничего не обнаружил. «Так-так, - сказал Иванов, - но «белую дыру» я все же открою».

7) Если в цепи будет большой перепад напряжения, то сгорит предохранитель, что повлечет за собой необходимость его замены. При целом предохранителе телевизор, конечно, будет работать, но только если он включен в сеть питания. Если телевизор работает нормально, то я увижу сегодняшние «Новости». Итак, я смотрю телевизионные «Новости» при условии отсутствия перепада напряжения и подключения телевизора к сети питания.

8) Уменьшение температуры приводит к снижению давления и уменьшению объема. Увеличение объема приводит к росту скорости потока. Повышение давления приводит к падению уровня, если при этом уменьшать температуру. Снижение скорости приводит к уменьшению давления или росту температуры. Технолог Иванов рассудил так: «Мне надо повысить давление при одновременном снижении скорости потока, поэтому я должен увеличить объем и температуру».

9) «Если знать язык программирования, то можно составить рабочую программу. Рабочую программу можно также получить при условии наличия знакомого программиста. Овладеть языком программирования можно, обучаясь в институте. Если программа работает, то ее написал выпускник такого института. Но программа не работает. Это говорит о том, что желающий получить правильный результат не знает языка программирования и не имеет знакомых программистов».

2. Вычислите значения выражений:

0) Ú b & a ¯ a ~	при а=1, b=0;
1) а ~ (b | ) Ú b &	при а=0, b=1;
2) | a Å b → а & b	при а=0, b=0;
3) (а | b) Ú & Å а	при а=0, b=1;
4) Ú b | a Ú a ~	при а=0, b=1;
5) а ~ (b → ) Å b ¯	при а=1, b=0;
6) ~ a Å b | а & b	при а=1, b=0;
7) (а Å b) | & Ú b	при а=0, b=0;
8) ¯ b & a Ú a ~	при а=0, b=0;
9) а | (b → ) Å b &	при а=0, b=0;

3. Постройте таблицы истинности формулы алгебры логики:

0) |b → & а 1)а → b Å a ¯ с 2)а Ú ¯ с → 3) |с 4)а → ¯	5)(a Å b) | Ú а 6) ¯ 7)а ¯ b Ú & 8)а & b | → с 9) → Å с ¯ а
a b с

Практическое занятие №7. Основы алгебры
логики

Задания для самостоятельного выполнения

1. Упростите формулы алгебры логики:

0)X ¯Y & X |	1)X → Y | &
2)X Ú Y ¯	3)X & → | Y
4)Y → Å Y ¯	5)X → YÅ |
6) ¯ & →	7) ¯ &
8)X Å Ú ¯X	9)Y → ¯

2. Определите, какие из формул являются тождественно истинными или тождественно ложными:

0) & Y ~ → º

1) ~Y & X Ú ÅY& X º

2) º

3) (X ~ ) Ú X Ú Y & ( Ú ) º

4) ~ Ú º

5) ((X Ú ) ® Y) & ( Ú Y) º

6) X ® Y ~ ® º

7) & Y ~ ~ → X º

8) & & X º

9) Y & X ® Y & X & Y º

3. Докажите равносильности, используя законы логики:

0) Ú (X Ú ) º X Ú

1) (X Ú Y) & () & ( Ú ) º Y &

2) X & Ú & Y & Z Ú X & Z º X & Ú Y & Z

3) (X Ú Y) & (X Ú ) º X;

4) (X & Y Ú Z) & (X Ú Y) Ú Z º X Ú Z Ú Y

5) Y Ú Y & º Y

6) Ú Y & X → Ú X º X Ú

7) Z Ú Y & ZÚ X & º Z Ú X;

8) Y Ú → YÚ X º X Ú Y;

9) Y & Ú º Y & ZÚ

Практическое занятие №8. Логические
функции

Цель занятия:	1.	изучить способы представления и суперпозиции логических функций;
	2.	привить навыки построения канонических форм логических функций;
	3.	изучить способы определения полноты системы логических функций.

Логической функцией называют функцию f(x₁,x₂, … x_n) аргументы которой x₁,x₂, … x_n и сама функция принимают значения 0 или 1. Для n = 0 – (нульарные функции) существует 2 различные логические функции, значения: константы И и Л;

n = 1 (унарные функции) существует 4 различных логических функций, значения:

g₁(x)=Л; g₂(x)=x, g₃(x)=x, g₄(x)=И,

n = 2 (бинарные функции) существует 16 различных логических функций:

f₁(x,y)=0=g₁(0) f₅(x,y)=Ø(y ® x)

f₂(x,y)=x & y f₆(x,y)=y=g₃(y)

f₃(x,y)=Ø(x ® y) f₇(x,y)=x Å y

f₄(x,y)= x=g₃(x) f₈(x,y)=x Ú y

f₉(x,y)= Ø(x Ú y) f₁₃(x,y)=Øx=g₂(x)

f₁₀(x,y)= x ~ y f₁₄(x,y)= x ® y

f₁₁(x,y)=Øy=g₂(y) f₁₅(x,y)= Ø(x & y)

f₁₂(x,y)= y ® x f₁₆(x,y)= 1=g₄(1)

n = 3 существует 256 различных логических функций и т.д.

Существуют три вида представления логических функций: аналитический (формула), табличный и в виде функциональной схемы и две канонические формы представления: нормальная и совершенная. Классы совершенных форм: совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ) и совершенная полиномиальная нормальная форма (СПНФ).

Механизм построения СДНФ:

1. постройте таблицу истинности логической функции;

2. отметьте наборы переменных, на которых логическая функция истинна;

3. выпишите отмеченные наборы переменных, соединяя между собой операцией конъюнкции, а между наборами – дизъюнкцией. Причем, если переменная имеет ложное значение, то она берется с отрицанием, а если истинное значение, то без отрицания;

4. упростите полученную формулу.

Механизм построения СКНФ:

1. постройте таблицу истинности логической функции;

2. отметьте наборы переменных, на которых логическая функция ложна;

3. выпишите отмеченные наборы переменных, соединяя между собой операцией дизъюнкции, а между наборами – конъюнкцией. Причем, если переменная имеет ложное значение, то она берется без отрицания, а если истинное значение, то с отрицанием;

4. упростите полученную формулу.

Механизм построения СПНФ заключается в замене:

a Ú b= a + b + ab, Øа = 1 + а из СДНФ.

Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Итог такой операции - суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности.

Система булевых функций {f₁, f₂, …,f_n} называется полной, если произвольная булева функция может быть выражена через функции f₁, f₂, …,f_n. Полной является система функций {Ø, &, Ú}.

Теорема о полноте. Если даны две системы логических функций F1, F2 и F1 полна, то система F2 полна тогда, когда каждая функция системы F1 представима через функции F2.

Дата добавления: 2014-11-20