- 26.07.2016
- 2506
- 26
Выбранный для просмотра документ Мат логика (задачник).pdf
ОБРАЗОВАТЕЛЬНАЯ АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ
ОРГАНИЗАЦИЯ
«ВОЛЖСКИЙ УНИВЕРСИТЕТ ИМ. В.Н. ТАТИЩЕВА»
(ИНСТИТУТ)
Кафедра «Прикладная математика»
УТВЕРЖДАЮ
Проректор по учебной работе
_______________А.Д. Немцев «___» _____________ 200__г.
Задачник по математической логике
Учебно-методическое пособие
Тольятти 2006 г.
Каверина И.А. Задачник по математической логике. Учебно-методическое пособие.- Тольятти: Волжский университет им. В.Н.Татищева, 2006, -50 с.
Учебно-методическое пособие разработано для специальностей 071900 «Информационные системы», 220100 «Вычислительные машины, комплексы, системы и сети» дневного и заочного отделений в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования.
Учебно-методическое пособие обсуждено и рекомендовано к изданию решением кафедры «Прикладная математика» протокол №___ от «____»_____________200___г.,
Зав. кафедрой «Прикладная математика» Каверина И.А.
Одобрено Учебно-методическим советом факультета
«____»______________200____ г., протокол №___
Одобрено Учебно-методическим советом университета
«____»______________200____ г., протокол №___
Председатель УМС ___________________А.Д. Немцев
©Волжский университет им. В.Н. Татищева
Каверина И.А. Задачник по математической логике. Учебно-методическое пособие.- Тольятти: Волжский университет им. В.Н.Татищева, 2006, 50 с.
Методический сборник разработан в соответствии с государственным образовательным стандартом дисциплины “Математическая логика и теория алгоритмов”. Содержит необходимые сведения теоретического характера, раскрывает содержание основных разделов курса. Приводятся решения типовых примеров по основным разделам дисциплины и задачи для самостоятельного решения.
Для студентов очной и заочной формы обучения специальностей 071900 «Информационные системы», 220100 «Вычислительные машины, комплексы, системы и сети».
Библиогр. 12 назв.
Рецензент д.т.н., проф. С.В. Краснов
Утверждено Ученым советом ВУиТ
© Волжский университет им. В.Н.Татищева, 2006
§1. Булевы функции. Таблицы истинности................................................... 6
§2. Равносильность булевых функций........................................................... 9
§3. Преобразование булевых функций........................................................ 12
§5. Булева алгебра. Нормальные формы................................................... 21
§10. Исчисление высказываний (ИВ)........................................................... 42
Существует немало хороших задачников по математической логике, для студентов высших технических учебных заведений. Издавая новое учебное пособие данного профиля, естественно ответить на вопрос, что нового дает выпускаемый задачник, в чем его отличие от ранее издававшихся пособий и какие цели ставили перед собой его составители. Характеризуя в этом плане основные установки, принятые автором настоящего издания, отмечаем следующее.
Задачник основан на лекционном курсе, который автор читал для студентов специальностей 220100 «Вычислительные машины, комплексы, системы и сети» и 071900 «Информационные системы и технологии» в Волжском университете имени В.Н. Татищева, что отложило определенный отпечаток на состав материала и подборку задач. Учебник ориентирован на студентов программистских специальностей, которым по роду их занятий приходится иметь дело с конструированием и анализом нетривиальных алгоритмов.
Сборник задач включает следующие разделы: булевы функции и таблицы истинности, равносильность булевых функций, преобразование булевых функций, функциональная полнота, булева алгебра, нормальные формы, минимальные формы, алгебра Жегалкина, алгебра высказываний, предикаты, исчисление высказываний, машина Тьюринга.
Данный сборник задач ставит своей целью помочь студенту самостоятельно овладеть методами решения задач по дисциплине «Математическая логика и теория алгоритмов. Это определило структуру задачника, в каждом параграфе даны короткие теоретические сведения и приведены таблицы, шаблоны, формулы, необходимые для решения задач, приводится значительное число подробно разобранных примеров и задач с разъяснениями методов их решения; наконец большое количество задач предлагается для самостоятельного решения.
Среди решенных задач немало таких, которые можно было бы назвать типовыми; во всяком случае, ознакомление с ними позволяет студенту при самой минимальной помощи со стороны преподавателя овладеть основными методами решения задач данного параграфа. Это обстоятельство особенно важно для студентов, занимающихся заочно.
Как правило, в задачнике приводятся только простые задачи. Автор специально старался избежать задач повышенной трудности, так как ставил перед собой цель научить студента решать основные элементарные задачи, дать некоторый минимум, необходимый для усвоения студентом требований Государственного образовательного стандарта высшего профессионального образования по дисциплине «Математическая логика и теория алгоритмов».
Вместе с тем работа с настоящим пособием не закрывает возможности более углубленного изучения предмета.
Данное пособие будет полезно при самостоятельной подготовке студентов к практическим занятиям, контрольным работам, зачету по «Математической логике и теории алгоритмов».
Автор выражает благодарность профессору С.В.Краснову и доценту С.В. Каверину за рецензирование рукописи и сделанные замечания, а так же Е.А. Красницкой за помощь в подготовке данного учебного пособия к печати.
Булевой функцией y=f(x 1 ,x 2 ,…,x n ) от п переменных x 1 , x 2 ,...,x n называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1.
Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д.
Отрицание − булева функция одной переменной, которая определяется следующей таблицей истинности
|
x |
0 |
1 |
Обозначения |
|
f(x) |
1 |
0 |
|
Элементарные булевы функции двух переменных приведены в следующей таблице.
|
x |
0 |
0 |
1 |
1 |
название |
обозначения |
|
y |
0 |
1 |
0 |
1 |
||
|
f1(x,y) |
0 |
0 |
0 |
1 |
Конъюнкция |
x&y, x⋅y, x∧y, min(x,y) |
|
f2(x,y) |
0 |
1 |
1 |
1 |
Дизъюнкция |
x∨y, max(x,y), x+y |
|
f3(x,y) |
1 |
1 |
0 |
1 |
Импликация |
x →y, x ⇒ y, x ⊃ y |
|
f4(x,y) |
1 |
0 |
0 |
1 |
Эквивалентность |
x∼y, x ↔ y, x ≡y |
|
f5(x,y) |
0 |
1 |
1 |
0 |
Сумма по модулю_2 |
x⊕y, x+y |
|
f6(x,y) |
1 |
1 |
1 |
0 |
Штрих Шеффера |
x|y |
|
f7(x,y) |
1 |
0 |
0 |
0 |
Стрелка Пирса |
x↓y, x°y. |
С помощью суперпозиции элементарных булевых функций можно построить более сложные функции, которые могут зависеть от любого числа переменных. Запись булевых функций через элементарные булевые функции будем называть формулой реализующей данную функцию.
Для более компактной записи сложных функций введем следующие соглашения:
1) внешние скобки опускаются;
2) сначала производятся операции в скобках;
3) считается, что приоритет связок убывает в следующем порядке: ¬, (∧, |, ↓), ∨, (→, ⊕),
↔.
Для равносильных связок (в скобках) приоритет определяется слева на право.
Пример 1.1. Расставить скобки в формулах:
1) x∨y↔z⊕x ; 2) x↓y∨z ; 3) x⊕y)↔z→x∧y∨¬z .
Решение:1) в формуле x∨y↔z⊕x скобки расставляются следующим образом: ((x∨y)↔(z⊕x));
2) т.к. операция ↓ сильнее операции ∨ согласно замечанию имеем ((x↓y)∨z);
3) в формуле (x⊕y) ↔z→x∧y∨¬z используя введенное старшинство связок, получаем, что данная формула равносильна ((x⊕y) ↔ (z→((x∧y)∨(¬z)))).
Пример 1.2. Составить таблицы истинности для формул:
а) x ↔ y → (y ⊕ x); б) x | (( y ∨ z ) ↓ x ∧ z ).
Решение: а) используя введенное старшинство связок, получим, что данная формула
равносильна x ↔ (y → (y ⊕ x)) , а таблица истинности примет вид:
|
x |
y |
|
у⊕х |
|
x ↔ (y → (y ⊕ x)) |
|
0 0 1 1 |
0 1 0 1 |
1 0 1 0 |
0 1 1 0 |
0 1 1 1 |
1 0 1 1 |
б) составим таблицу истинности для формулы x | (( y ∨ z ) ↓ x ∧ z )
|
х у Z |
|
|
|
х∧ z |
x ∧ z |
(y ∨ z) ↓ (x ∧ z). |
F(х,у) |
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
1 1 0 0 1 1 0 0 |
1 0 1 0 1 0 1 0 |
1 1 1 0 1 1 1 0 |
0 0 0 0 0 1 0 1 |
1 1 1 1 1 0 1 0 |
0 0 0 0 0 0 0 1 |
1 1 1 1 1 1 1 0 |
Формула называется тождественно истинной (ложной), если она принимает значение 1 (0) при всех значениях входящих в нее переменных.
Пример 1.3. Является, ли формула
((х → у) ∧ у) → х тождественно истинной?
|
x |
y |
|
|
х→у |
|
|
|
0 0 1 1 |
0 1 0 1 |
1 1 0 0 |
1 0 1 0 |
1 0 1 1 |
0 0 0 1 |
1 1 1 1 |
Формула равна 1 при всех значениях входящих в нее переменных, следовательно, она тождественно истинная (тавтология).
1.1. Выясните, в каких случаях приведенные ниже данные противоречивы.
1. а=1, а ∧ b = 0. 8. а=1, а ↓ b = 1. 15. a=0, a ↓ b ↔ a =1.
2. а=1, а ∨ b = 0. 9. а=0, а ∧ b = 0. 16. b=1, a ⊕ b ∨ ab = 0.
3. а=1, а ∧ b = 1. 10. а=0, а ∨ b = 0 17. a=1, a ∨ ab → a ∨ b = 0.
4.
а=1, а ∨ b = 1. 11.
а=0, а ⊕b
= 1. 18.
a=1, b(a →
b)=1.
5. а=0, а ∧ b = 1. 12. а=0, а ↔ b = 0 . 19 a=0, a b∨ a =1.
6. а=0, а ∨ b = 1. 13. a=1, ā∨ b → ā = 1 20. b=1, a ⊕b∨ b = 0.
7. а=1, а↓ b = 0 . 14. а=1, а│b↓ā=1. 21. b=0, а ∨ b ∧ a → b = 0.
1.2. Найдите логические значения х и у, при которых выполняются равенства:
1.
(1→ x)→ y = 0 . 8.
(x
↔ 0)→ y = 0 . 15.(1→х) → у= x .
|
2. x ∨ y = x . |
9. х= x ∨ y . |
|
|
|
3. (x ↔ 0) → у=1. |
10. x ↔ y =1→ y . |
|
17. (1∧ x) → y =х∨ y . |
|
4. (x ∨1) ↔ у= 0. |
11. x ↓ y = y ↔ x. |
|
|
|
5. х ∨ (y ∧ x)= x. |
12. 0 → x ∨ y =1. |
|
19. у ∧(x ∨ y)= y. |
|
|
|
|
20. 21. х ׀y ∨ x ↓ y =1. |
1.3. Определите логическое значение формул.
1. x → y∨ xy, при х=1, у=1. 2. у⊕ху∨х, при х=1, у=1.
3. х⊕у∨х, при х=0, у=1.
4. (х ⊕ у)→ (ху
↓ х),
при х=0, у=0.
5. ху → х, при х=0, у=0. 6. (х ↔ у)(х ∨ у⊕ х), при х=1, у=0.
7. х ∨ ух, при х=1, у=1. 8. у ↔ ((x ∧ z)∨ (y ∧ z)), при х = 0, у = 1, z = 1.
9.
ху∨ху→х, при х=0, у=1. 10.
x ∧ (y
↔ z) ⊕ (x ∧ y) ↓х , при х
= 1, у = 0, z = 0.
11.
x ↓
(y → z)
↔ (x ∨ y) → (x ⊕ z), при х
= 0, у = 0, z = 1.
12. x ⊕ ( y → z ) ∨ (x → y) ↔ (x ↓ z) , при х = 1, у = 0, z = 0.
13.
x ∧(y
→ z)↔ (y
⊕ z)∨ x | (( y ↔ z ) ↓ x ∧ z ) , при х = 0
, у = 1, z = 0.
14. ((x ⊕ y)∧ z)↓ ((x → z) (∨ y ↔ z)), при х = 0, у = 1, z = 0.
15.
((x ↓ y)∧ z)→((x
∧ z)↔ (y
∨ z)),
при х = 0, у = 1, z = 0.
16. (x ∨ y) → (x ↔ z) ⊕ x ↓(y → z), при х = 1, у = 0, z = 0.
17. x ↔ (y → z) ∧ (x ∨ y) ⊕ (x ↓ z) , при х = 0, у = 0, z = 1.
18.
x ⊕
( y ↓
z ) ∨
(x ∧ y)
→ (x ↓ z) , при
х = 0, у = 1, z = 0.
19.
x | (( y ∨
z ) ↓
x ∧
z ) ∧ x ∧(y
→ z)↔ (y
⊕ z),
при х = 0 , у = 0, z = 1.
20. ((x ↓ y)∧ z) → x | (( y ⊕ z ) ↔ x ∨ z ). , при х = 0, у = 1, z = 1.
1.4. Составить таблицу истинности данной булевой функции:
1.5. Известно, чтоимпликация х→у истинна, а эквивалентность х↔у ложна. Что можно сказать о значении импликации у→х?
1.6. Проверить, не составляя таблиц истинности, являются ли следующие формулы тождественно истинными:
1.
р→р.
6. р→
р . 11. р∨
(р↔ р).
16. р∨ p
→ p.
2. р∨ р. 7. р↔ р. 12. р∨ р. 17. (р→р)∨q.
3.
р∧ р . 8.
(р
∨ р)
→ р.
13. (р→ р)∨ р. 18.
(0
→ p)
(∨ q →1).
4. р↔ р. 9. р∧(р⊕ р). 14. р↔ (р→ (р↓ р)). 19. (p →1)∨ q.
5.
0 →
p. 10. p p ∨
p. 15. р↔
p∨ p.
20. (р ∨
p)∨ q.
1.7. Учитывая соглашения о порядке выполнения операций,
а) опустить «лишние скобки и знак «∧» в формулах:
|
1)
2)
3) ((х ∨ у)∨ z)→ ((х ∧ у)∨ z); |
6)
7)
8) (х ∧(у∨ z))∧((х → (у → z))↔ (х ∧ у)); |
|
|
|
5) ((х∨ у)∨(х∨((у∧(х∨ z))
(∧ у → z)))↔ z); 10) ((((х∧у)z))∧z)↔(((х∧у)∧z)∧((х∨у)∧z));
|
1) х ∨ у → х; |
|
6) х│у(х → х ∨ уz) ↔ (х ∨ у → х ⊕ уz); |
|
2) х∨у→х⊕у; |
|
|
б) восстановить скобки и знак «∧» в формулах:
3) ху∨ху(у∨ z); 8) х ↓ у → х ∨ у(х
→ z)∨ х(у
↔ z);
4)хz ∨ у(х
⊕ у ∨ z);
9) х│уz → (х
↔ уz)∨ х ⊕ у ↓ z(х
→ (у
↔ z));
5) ху ∨ хуz → ху ∨ уz; 10) х ∨ у ↔ х(у
→ z)(х
↓ у)∨ х ∧ z ∨ уz.
Булевы функции f1 и f2 называются эквивалентными, если на всяком наборе (a1, a2,…, an) нулей и единиц значения функций совпадают. Обозначение эквивалентных
(равносильных) функций следующее: f1=f2 или f1≡f2.
Основные эквивалентности (H, H1, H2, H3… означают некоторые булевы функции):
1. Закон двойного отрицания: H = H .
2. Идемпотентность: HH=H, H∨H=H.
3. Коммутативность: H1∗H2=H2∗H1, где символ ∗ означает одну из связок &, ∨, ⊕, ∼, |, ↓.
4. Ассоциативность: H1∗(H2∗H3)=(H1∗H2)∗H3, где символ ∗ означает одну из связок &, ∨, ⊕, ∼.
5. Дистрибутивность: H1&(H2∨H3)=(H1&H2)∨(H1&H3), H1∨(H2&H3)=(H1∨H2)&(H1∨H3).
6. Законы де Моргана: H 1 & H 2 = H1 ∨ H 2 , H 1 ∨ H 2 = H 1 & H 2 .
7. Правила поглощения: H1∨(H2&H1)=H1, H1&(H2∨H1)=H1
8.
Законы склеивания:
H1 &H2 ∨H1 &H2 =H1, (H1∨H2)&(H1 ∨H2)=H1.
9. Законы инверсий: H ∨ H = 1, H & H = 0.
10. Правила операций с константами: H∨1=1, H&1=H, H∨0=H, H&0=0.
Все приведенныесоотношения легко проверяются по таблицам истинности. Пример 2.1. Упростить формулы, используя основные законы эквивалентности:
х→у=х∨у (6) х → у
2) (х→у)∧у→х = ¬((х→у)∧у)∨х = (¬(х→у)∨¬у)∨х
(3) (2) х → уу
=(х∧¬у∨¬у)∨х = (¬у∨¬у∧х)∨х = ¬у∨х у→х.;
3)
xyz ∨
xy ∨
xyz ∨
xz ∨
xz ==
xz(y ∨ y)∨
xy ∨
xz ∨
xz =
xz ∨
xy ∨
xz ∨
xz =
=
(xz ∨ xz)∨
(xz ∨ xz)∨
xy =
x(z ∨ z)∨
z(x ∨ x)∨
xy =
x ∨
z ∨
xy =
x(1∨ y)∨
z =
x ∨
z;
4)
⋅
x1 ∨ x2x3 ⋅ x1x2 ∨ x3 = х0(х2 ∨ х3) ∨ (х1х2)х3 = (x1 ∨ x2x3) ∨ (x1x2 ∨ x3) = х1(х2 ∨ х3)
= x1 ∨ x2x3 ∨ x1 ∨ x2 ∨ x3 = x1 ∨ x2 ∨ x3.
Пример 2.3. С помощью равносильных преобразований упростить формулу
⎧а)х ∨ (у ∨ z) ≡ х → (у ∨ z);
⎪
⎪б)z ∨ (х
∨ у)
≡ z → (х
∨ у);
⎪
≡ ⎨в)у ∨ х ∨ z) ≡ у ∨ хz;
⎪
⎪г)х ∨ z ∨ у ≡ хz ∨ у ≡ хz → у;
⎪
⎩д)х ∨ у ∨ z ≡ хуz.
Любую запись а)-д) можно считать ответом.
Пример 2.4. Проверьте, будут ли эквивалентны следующие функции: (х → z)(у → z); (х ∨ у)→ z.
С помощью равносильных преобразований получаем, что
(х → z)(у
→ z)
≡ (х
∨ z)(у
∨ z)
≡ ху ∨ zу ∨ хz ∨ z ≡ ху ∨ z ≡ х ∨ у ∨ z ≡ (х
∨ у)
→ z, т.е. функции
эквивалентны.
Пример 2.5. Доказать равносильность
(х∨у) ∧ (х∨у) ≡х.
(х ∨ у) ∧ (х ∨ у) ≡ х ∧ х ∨ у ∧ х ∨ х ∧ у ∨ у ∧ у ≡ х ∨ у ∧ х ∨ х ∧у ≡ х ∧ (1∨ у ∨ у) ≡ х ∧ (1∨1) ≡ х.
2.1. Доказать следующие равносильности:
1.
х ∨
у ≡ х ∧ у. 8. х ∨ у ≡ х ↓ у.
2.
х ∧ у ≡ х у. 9.
x y ≡ x ∨ y. .
3.
x ↓ y ≡ x ∧ y. 10. (x
∨ y)∧ (x
∨ y)≡ x. 17. x ⊕ (y ⊕ z) ≡ (x ⊕ y) ⊕ z .
4.
x y ≡ x ∨ y . 11.
x ∨ (x
∧ y)≡ x ∨ y. 18. ху
→ (х
∨ у)z
≡ хуz .
5.x → y ≡ y → x. 12. ху → z ≡ х ∨ у ∨ z. 19. x → (y → z) ≡ x∧ y → z .
6.
x →
y ≡ x∨ y . 13.x
⊕ y = x ∧у ∨ х ∧ y. 20 х→у≡1⊕у⊕ху.
7. x ∨ (у ∧ х) ≡ x . 14. (х ∨ у)(х ∨ у) ≡ х. 21. x ↔ y ≡ (x ∨ y)(x ∨ y).
2.2. 
Показать, чтоформулы b → a , a∧b → a , a∧b → b имеют ту же таблицу истинности,
что и импликация a→ b.
2.3. Проверьте, будут ли эквивалентны следующие функции.
1.
x
→ (y ⊕ z), (x → y) ⊕ (x → z). 11. x
↓ (y ∧ z) , (x
↔ y)∨ (x
∨ z).
2. x ∧ (y ⊕ z), (x ∧ y)⊕(x ∧z). 12. (у∨ x) ⊕ (y ∧ z) , (x ⊕ y) (∨ x ⊕ z).
3. x ∧(y ↔ z), (x ∧ y) ↔ (x ∧z). 13.х⊕у,у⊕х.
4.
x ∨ (y | z),(х
∨ у)(х
∨ z).
14. х ∨
у,х ↔ у.
|
8. x ∨ (y → z), (x ∨ y) → (x ∨ z). |
|
18. х ∧ у ∧ х,х. |
|
9. х ⊕ (у → z) (, ху) ↔ (х ⊕ z). |
|
19.ху ↓ z,z ↓ ху. |
|
10. x ↓ (y ↔ z), (x ↓ y) ↔ (x ↓ z). |
|
20. х ∨ yz,(х ∨ у)(х ∨ z). |
5.
x ⊕ (y → z), (x → y) ↔ (x ↓ z). 15.х ∨ у, ху.
|
6. x | (y → z), (x | y) → (x | z). |
|
16. х ∧ у,х ↓ у. |
|
|
|
17. х(у ∨ х), х. |
2.4. Преобразуйте формулы, используя основные законы эквивалентности:
1. ху ∨ у ∨ ху. 2.
х ∨ у ∨ ху ∨ ху .
3.
|
4. х ∨ у ∨ ху ∨ у ∨ ху.
5.хуz ∨ xy ∨ xyz ∨ yz. 15. хуz ∨ x ∨ y ∨ z ∨ хy ∨ xyz.
6.
хуz ∨
x ∨ y ∨ z ∨ yz ∨ xyz . .
7. хyz ∨ yz ∨ xy ∨ x ∨ y.
.
9.
2.5. Преобразовать следующие формулы так, чтобы знак отрицания был отнесен только к переменным.
8)
(х ↔
у)(у
↔ z);
9) (х → у)(у → х);
10) хуz(х → у);
11) хуz ∨ хуz;
12) хуz ∨ (х → t)∨ хуzt;
6)
х → (у
→ z);
13) (х ∨
у)(z
∨ t)(х
∨ у);
20)ху ∨ z
∨ t ∨ х ∨ у;
7) х → у → (х → z); 14) ((х ∨ у)z)(х ∨ уz)(у ∨ t).; 21)хуzt ∨ х ∨ (х ∨ zt).
Пример 3.1. . Используя основные эквивалентности упростить формулы:
1) (x ∨ y⋅z)⋅(x →y⋅z)⋅(x →(y ↔z))=
⎛ ⎞ (x ∨ (y ↔ z))=
(x(y ∨ z)∨
x(y ∨ z))⋅(x ∨ yz∨ yz)=
=⎜x ∨
yz ∨
x ∨
yz⎟⋅
⎝ ⎠
= (xy ∨ xz ∨ xz)⋅(x ∨ yz∨ yz)= x ⋅(x ∨ yz∨ yz)= x;
2) ((x →y) (~ y→(x →z)))⊕ x⋅(y⋅z)=
= ((x ∨ y)
~ (y
∨ x ∨ z))⊕ xyz = ((xy
⊕ x ⊕ y)⊕ xyz)⊕ xyz = xy ⊕ y ⊕ x ⊕ y ⊕ xy = x.
⎛ ⎞ (х2
∨ х3(х4
∨ х5 )).
3) х1 ∨ х2 ∨ х3 ∨ х4 ∨ х5 = х1⎜х2 ∨ х3 ∨ х4 ∨ х5 ⎟ = х1
⎝ ⎠
Пример 3.2. Доказать эквивалентность следующих функций:
(x → (y
→ (x
~ z)))⋅(x
~ (y
→ (z
∨ (x
→ y)))) и (x → (y
→ z))→ x .
Решение. Преобразуем обе функции.
(x → (y
→ (x
~ z)))⋅(x
~ (y
→ (z
∨ (x
→ y))))
=
=(x
∨ y∨(x
~ z))⋅(x
~(y∨ z∨ x ∨ y))=(x
∨ y∨ xz∨ xz)⋅(x
~1)=(x
∨ y∨ z)&x
= x.
(x → (y
→ z))→ x = x ∨ y ∨ z ∨ x = xyz ∨ x = x .
Так как, правые части функций равны, то отсюда следует, что функции эквивалентны.
Пример 3.3. Доказать, что (х → у)→ ((у → z)→ (х∨ у → z))≡1. Для доказательства тождественной истинности формулы запишем цепочку равносильных формул:
(х → у)→((у → z)→(х ∨ у → z))=
(х ∨ у)→
((у∨ z)→
(х ∨ у∨ z))≡
≡ х ∨
у∨
(у∨ z ∨ х ∨ у∨ z)≡
х & у∨
у& z ∨
х & у∨
z ≡
(х & у)∨
х & у)∨
∨
(у&z)∨
z ≡
(х ∨ х)& у∨ (у∨ z)&(z ∨ z)≡
(у∨ у)∨
z ≡1∨ z ≡1.
Пример 3.4. Построить релейно-контактную
схему для формулы f(х,у)=ху ∨
ху.
f (х, у, z) = хуz ∨ хуz ∨ хуz ∨ хуz.
Упростим РКС используя
равносильности H ∨ H
≡ H,H ∨ H ≡ 1.
f(x, y,z) = (хуz ∨ хуz) ∨ (хуz ∨ хуz) ∨ (хуz ∨ хуz) ≡ уz(х
∨ х)∨ хz(у
∨ у)∨ xy(z
∨ z)
≡
≡ уz ∨ хz ∨ ху ≡ (у ∨ х)z ∨ ху.
Последняя формула соответствует схеме
3.1. Используя основные эквивалентности и задачу 2.2 упростить формулы:
1. (х → х) → х . 11. х ∨ уz ∨ (ху ∨ уz)∨ у.
2.
(х↔ у) ∧ (х∨ у). 12.
ху ∨ (х
∨ у)∨ хуz ∨ уz.
3.
х ∧ у ∨(х → у) ∧ х . 13.
уz ∨ хуz
∨ (х
∨ уz)∨ хуz.
4. xz(y ∨ y)∨ xy ∨ xz ∨ xz . 14. (х ⋅ уz ∨ t )∨ zt ∨ (ху ∨ z).
5.
xyz ∨ xy ∨ xyz ∨ xz ∨ xz. 15.
(х
↔ у)
↓ (х
∨ ху ∨ уz ∨ хуz).
6. (xz ∨ xz)∨ (xz ∨ xz)∨ xy. 16. хуz ∨ (ху ∨ хуz ∨ уz)х.
7.
(х ∨ у)∧ (х
∨ у)∧ (х
∨ z).
17. ((х
⊕ у)→ (х
∨ у))((х
→ у)→ (х
⊕ у)).
8.
ху ∨
(хуz
∧ ху)∨ ху.
9.
(у ∨ z ∧ z)∧ х ∨ z ∧ у. .
10.
х ∧ (х
∧ у ∨ z)∨ уz ∨ хуz. 20.
(ху
∨ хz)(у
∨ z)∨ ху.
3.2. Используя законы логики, преобразуйте данные формулы:
1. хуz ∨ ху ∨ х ∨ хуz. 11. yz ∨ xyz ∨ уz ∨ ∨xy ∨ zу ∨ xyz .
2. уz ∨ хуz ∨ хуz ∨ ху ∨ z. 12. (x ∨ y ∨ уz)(x ∨ yz)(xz ∨ z ∨ xyz ∨ y).
3. уz ∨ (уz ∨ хуz)∨ ху ∨ хуz. 13. yx ∨ xyz ∨ xy ∨ xyz ∨ xy ∨ yz ∨ xyz .
4.
хуz ∨ ху ∨ (уz
∨ хуz)∨ хz. 14.
xz ∨ xyGz ∨
yz ∨ xyz
∨ yz ∨ xy .
5. xyz ∨ xy ∨ yх ∨ xyz ∨ хyz ∨ yz . 15. xyGz ∨ xyz ∨ xyz ∨ xyG ∨ yzG ∨ xyz .
6. xyz ∨ xyz ∨ xy ∨ x ∨ yz ∨ xyz ∨ xy . 16. xyz ∨ y ∨ xyz ∨ xz ∨ xyz ∨ x ∨ xyz .
7. xyz ∨ xy ∨ xyz ∨ x ∨ y ∨ xyz ∨ xyz . 17. хуz ∨ ху ∨ (уz ∨ хуz)∨ хуz.
8. xz ∨ xy ∨ yz ∨ xyz ∨z ∨ xy ∨ xyz . 18. уz ∨ хуz ∨ хуz ∨ ху ∨ уz ∨ хуz ∨ уz.
9. z . 19. (х ∨ уz)∨ х ∨ ху ∨z ∨ хz.
20. хуzt ∨ хt ∨ уzt ∨ хуt.
3.3.. Составьте РКС для формул
1. ху ∨ ху ∨ ух. 12. z ∨ xy ∨ xyz ∨ xy ∨ xyz ∨ y z.
2.
хуz ∨ хуz ∨ z. 13. xz
∨ xyz ∨ xyz ∨ yz ∨ xy ∨ x ∧ z .
3.
хуzt ∨ уzt ∨ х. 14.
хуzt ∨ хуt
∨ (у
∨ t(х
∨ уt)).
4. xyz∨ ху ∨ xyz . 15. ((x → y) ∧ (y → z)).
5.
xyz ∨
y ∨ xyz
∨ xz .
16. х ∧
z → (y
∨ x) .
6.
xyGz
∨ xyz ∨ xyz ∨ x . 17. х
∧ у → (z ∨ x). 7.
(х
∨ у)z
∨ ху. 18.
xz ∨ xzy
∨ xy ∨ xyz .
8.
(х ∨ у)∨ (ху
∨ z).
19. x ∨
yz ∨ xz
∨ xyz ∨ z ∨ yz .
9. х(у ∨ z)∨ хz ∨ (х ∨ у)z. 20. yz ∨ xyz ∨ xyz ∨ xy ∨ z ∧ xy ∨ y.
10.
xyz ∨ xy ∨
yz ∨ xуz
∨ xz .
21. х yz ∨ xz
∨ yz ∨ xy ∨ хуz ∧ xy ∨ y.
11. (уz ∨ t)∨ ((хуz ∨ хуz)∨ у ∨ z).22) z ∨ xyz ∨ xyz ∨ xy ∨ yz ∧ y ∨ xyz .
3.4.Найти функции проводимости (другие названия − переключательные функции, булевы функции) следующих релейно-контактных схем, если возможно упростите схемы: Есть ли среди приведенных схем - эквивалентные?
3.5.Какие из приведенных формул являются тождественно истинными или тождественно ложными:
1. х ↔ х. 12. ((х ⊕ у) ↔ z)(х → уz).
2. х ∨ х. 13. (х → у)→ ((хх ∨ z)→ (у ∨ z)).
3.
х ∧ х. 14.
((х
→ z)∧ (у
→ z))→ ((х
∨ у)→ z).
4. х ↔ х. 15. (х → (у → z))→ ((х → у)→ (х → z)).
5. х → (у → х). 16. ((х ∨ у)∧ х)→ у.
6.
х → (х → у).
17. ((х ↔
у)∧ х)→ у.
7.
х(х
∨ у)
↔ ху.
18. (х
→ у)
↔ (у
→ х).
8. ((х → у)∧ х)→ у. 19. (х ↓ у)z ↔ (х → у)z.
9.
(х → у)
↔ (у
→ х).
20. ((х →
у)∧ (у
→ z))→ (х
→ z).
10. ((х
→ у)∧ у)→ х. 21. (х
→ (у
→ z))→ ((х
∧ у)→ z).
11. (х → у)z ∨ (х → у)z.
3.6. Доказать эквивалентность следующих функций:
1)
(x
→ y)⊕ ((y
→ z)→ x ⋅ y),
y & z → x ;
2)
(x ∨ y)
↓ (x
→ (y
→ z)),
y → (x ∨ z) ;
3) x → ((y → z)→ y ⋅ z), (x ∨ (y → z))⋅(x ⊕ y);
4)
(x ↓ y)∨ (x
↔ z)|
(x
⊕ y ⋅ z),
x ⋅(y
⋅ z)∨ x → z ;
5)
((x ∨ y)⋅ z → ((x
↔ z)⊕ y))⋅((x
⊕ y)⋅ z),
(x
→ yz)x
→ y ;
6)
(x
∨ y)→ ((y
| z)→ (x
↔ x ⋅ z)),
xy ∨ (x
→ xy → z);
7)
(x | y)
→ ((y
↓ z)→ (x
⊕ z)),
x ⋅(y
⋅ z)⊕ (x
→ z);
8)
(((x | y)
↓ z)|
y)↓ (y
→ z),
((x
| y)
↓ (y
| z))⋅(x
→ (y
→ z));
9) (x ⋅ y → z)∨ ((x ↓ y)| z), ((x → y ⋅ z) ⊕ (x ↔ y)) ∨ (y → x ⋅ z);
10)
x ⊕ y ⋅ z ⋅y → x ⋅ z ⋅(x
↓ y), (xy → (y
↓ z))∨ x ⋅ z ⋅;
11)
(x
→ y)→ (x
⋅ y ↔ (x
⊕ y)),
(x
⋅ y → x)→ y ;
12) (x ⋅ y ∨ (x → y ⋅ z)) ↔ ((x → y)→ z), (x → y)⊕ (y ⊕ z);
13)
(x ⊕ y ⋅ z)→ (x
→ (y
→ z)),
x → ((y
→ z)→ x);
14) ((х│х)│(у│у))│((х│х)│(у│у)), х ↓ у;
15)
(x ∨ y ⋅ z)→ ((x
→ y)→ ((y
∨ z)→ x)),
(x
→ y)→ (y
→ x);
16)
(x ⋅ y ∨ x ⋅ z)⊕ ((y
→ z)→ x ⋅ y),
(x
⋅(y
⋅ z)⊕ y)⊕ z ;
17) x → ((x ⋅ y → (x ⋅ z → y))→ y)⋅ z , x ⋅(y → z);
18)
(x
↔ y)
→ (x
→ z)∨ (x
⊕ y ⋅ z),
x ↔ (z
→ y);
19)
(х ↓ у) ⊕ ((х у) ↓ (х ↔ уz) , ху ∨ ху ∨ уz ;
20) ((x ∨ y) → y ⋅ z) (∨ y → x ⋅ z)∨ (x → (y → z)), (x → y)∨ z .
Классы Поста.
1. Класс функций, сохраняющих константу 0, т.е. таких функций y=f(x 1 ,x 2 ,…,x n ), что f(0,0,…,0)=0. Например, x∨y(¬x).
2. Класс функций, сохраняющих константу 1, т.е. таких функций y=f(x 1 ,x 2 ,…,x n ), что f(1,1,…,1)=1. Например, x∨¬(yx).
3. Класс самодвойственных функций, т.е. таких функций y=f(x 1 ,x 2 ,…,x n ), что
f(x 1 , x 2 ,… , x n ) = f( x 1 , x 2 ,… , x n ) .
4. Класс линейных функций, т.е. таких функций y=f(x 1 ,x 2 ,…,x n ), которые могут быть представлены в виде f(x 1 ,x 2 ,…,x n )=c 0 ⊕ c 1 x 1 ⊕ c 2 x 2 ⊕ … ⊕ c n x n , где с0, c1, c2…коэффициенты, которые могут принимать значение 0 или 1.
5. Класс монотонных функций. На множестве наборов из нулей и единиц введем частичный порядок следующим образом: (a1,,a2,...,an)≤(b1,b2,...,bn) тогда и только тогда когда a1≤b1, a2≤b2,…,an≤bn. Функция f(x1, х2,...,хn) называется монотонной, если для любых двух элементов таких, что (a1,,a2,...,an)≤(b1,b2,...,bn) следует, что f(a1,,a2,...,an)≤f(b1,b2,...,bn).
Система S булевых функций, суперпозицией которых может быть представлена любая булева функция, называется функционально полной, а функции из S образует базис.
Критерий полноты (Теорема Поста). Система S булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.
1. Система функций S1={¬,∧,∨} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности:
x → у = x ∨ y , x ↔
y =
(x ∨
y)(x ∨
y) , x ⊕ y = x y ∨ x y , x | y = x ∨ y , x ↓ y = x & y .
2. Система S2={¬,&} образует базис. Произвольную функцию можно сначала привести к
виду, содержащему связки из S1 а затем использовать соотношение x ∨ y = x ⋅ y .
3. Система S3={¬,∨} образует базис. Произвольную функцию можно сначала привести к
виду, содержащему связки из S1 а затем использовать соотношение x ⋅ y = x ∨ y .
4. 
Система S4={1,&,⊕} образует базис. Произвольную
функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать
соотношения x =
1 ⊕
x , x ∨
y =
x ⊕
y ⊕
x ⋅
y .
5.
Система S5={|} образует базис. Произвольную
функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать
соотношения x ⋅
y =
x y ,
x
=
x 
x .
6.
Система S6={↓} образует базис. Произвольную
функцию можно сначала привести к виду, содержащему связки из S3 а затем использовать
соотношения x ∨
y =
x ↓
y , x = x ↓ x .
Примеры 4.1. Записать функцию x↔(y⊕z) в базисе S1={¬,∧,∨}.
x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅ (x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅ (x ∨ y ⋅ z ∨ y ⋅ z) .
Примеры 4.2. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g (определена ниже) двойственной к функции f=(¬x→¬y)→(y→x).
f* =(x → y)→(y → x)=
x ∨
y∨(y∨ x)=
1 =
0 , g = (x
∨ y)&
(y
∨ x)= x → y ≠ 0. Значит, g не
двойственна к f.
Пример 4.3. Используя критерий полноты (теорему Поста) проверить, является ли полной
система функций S={f1,f2}: f1 = x ∧ y; f2 = x → y.
Решение: Проверим какими свойствами обладают данные функции.
1. Сохранимость константы 0. f1(0,0)=0⋅1=0 – сохраняет константу О.
f2(0,0)=0 → 0 =1→1=1 – не сохраняет константу 0.
2. Сохранимость константы 1. f1(1,1)=1⋅0=0 – не сохраняет константу 1. f2(1,1)=0→0=1 – не сохраняет константу 1.
3. Самодвойственность.
f1(x, y) = x ∧ y = x ∨ y = x ∨ y ≠ f1(x, y) = x ∧ y – не самодвойственна.
Составим таблицы истинности для функций: f2(x,y)= x→y= x→ y, и f2(x, y) = x → y.
|
х у |
х→у |
х → у |
х |
у |
х → у |
|
0 0 0 1 1 0 1 1 |
1 1 0 1 |
0 0 1 0 |
1 1 0 0 |
1 0 1 0 |
1 0 1 1 |
Из таблицы истинности видно, что f2(x, y) = x → y ≠ f2(x,y)= x→y т.е. f2-не самодвойственна.
4. Линейность. Построим полином Жегалкина для функции f2 методом неопределенных коэффициентов. P(x,y) имеет вид: P(x, y) = c0 ⊕ c1 ⊕ c2y ⊕ c3xy.
Используя таблицу истинности для f2, полученную в п.3, имеем P(0,0)=C0=1 ⇒ C0=1,
P(0,1)=C0 ⊕C2=0 ⇒ 1⊕C2=0 ⇒ C2=1, P(1,0)=C0 ⊕C1=1 ⇒ 1⊕C1=1 ⇒ C1=0,
P(1,1)=C0 ⊕C1 ⊕C2 ⊕C3=1 ⇒ 1⊕0⊕1⊕C3=1 ⇒ C3=1. Итак, f2=1⊕y⊕xy – не линейна.
5. Монотонность. Очевидно, что наборы упорядочены следующим образом:
(0,0)≤(0,1); (0,0)≤(1,0); (0,0)≤(1,1); (0,1)≤(1,1); (1,0)≤(1,1).
Проверим на монотонность функцию f1:
f1(0,0)=0⋅1=0 ≤ f1(0,1)=0⋅0=0; f1(0,0)=0 ≤ f1(1,0)=1⋅1=1; f1(0,0)=0 ≤ f1(1,1)=1⋅0=0; f1(0,1)=0⋅0=0 ≤ f1(1,1)=1⋅0=0; f(1,0)=1⋅1=1 ≥ f1(1,1)=1⋅0=0.
Итак, мы получили, что для (1,0)≤(1,1), не выполняется f1(1,0)≤f1(1,1), следовательно, функция f1–не монотонна.
Проверим на монотонность функцию f2(0,0)=1; f2(0,1)=0. Итак, для (0,0)≤(0,1) мы не получили что f2(0,0)≤ f(0,1). Следовательно, f2–не монотонна.
Сведем наши вычисления в таблицу.
|
Функция |
Не сохр.0 |
Не cохр.1 |
Не cамодв. |
Не линейность |
Не монотонность |
|
f1 f2 |
* |
* |
* * |
* * |
* * |
Из теоремы Поста, заключаем, что система S = {x ⋅ y, x → y}– полная.
Пример 4.4. Найдем все импликанты и простые импликанты для формулы f=x→y. Всего имеется 8 элементарных произведений с переменными х и у. Ниже, для наглядности, приведены их таблицы истинности:
|
x |
y |
x→y |
|
|
|
x ⋅ y |
|
|
x |
y |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
Из
таблиц истинности заключаем, что формулы x ⋅
y , x ⋅ y
, x ⋅ y , x ,y—
все импликанты формулы x→y,
а из этих импликант простыми являются формулы x и у (формула x ⋅ y , например, не является
простой импликантой, поскольку, отбрасывая литеру y , получаем импликанту x ).
4.1. Используя теорему Поста покажите, что следующие системы не являются полными. 1) {¬, 1}}, 2) {∧, ∨}, 3) {⊕,¬}. 4) {⊕,1}, 5) {⊕,∧}, 6) {~,∧}, 7) {∨,→}, 8) {~,∨},
9) {¬,→}, 10) {→,~}, 11) {¬,~}, 12) {∧,→}.
4.2. Следующие формулы преобразовать так, чтобы они содержали только а) {¬, ∧}}, б) {¬, ∨}}, в) {∧,∨,¬}.
1. х ∨ у. 8. х ↔ y ↔ z. 15. (х → у) ↔ (y → х).
2. х ∧ у. 9. хy ↔ хz. 16. (х ↔ у)(y ↔ z) → (х ↔ z).
3. х ↔ у . 10. х ∨ (х ↔ y). 17. х ↔ y ↔ z ↔ t.
4.
х →
у . 11. х →
у ∨ (х → y). 18. х ⊕ yz → (y ∨ z).
5. х ∨ y ∨ z. 12. (х ↔ у) (y ↔ z). 19. (х ↔ у) ∨ (y ↔ z) → (х ↔ у ↔ z).
6.
хyz
. 13. хy →
(y → x). 20.
(х → у) ↔ (х → (х ↔ z)).
7. х(y ↔ z). 14. х ∨ у → (х → z). 21. х(y ⊕ z) → (х ∨ z).
4.3. Используя критерий полноты (теорему Поста) проверить, является ли полной система функций S={f1,f2}.
1. f1 =
x ∨ y, f2 = x ⊕ y. 8. f1 = x ↔y, f2 = xy. 15. f1 = x ⊕ y, f2 = x ∨ y.
2. f1 = x ↔ y, f2 = x y. 9. f1 =x→y, f2 =x∧y. 16. f1 = x ↔ y, f2 = x y .
3. f1 =x →y, f2 =x ∧ y. 10. f1 =х y, f2 =x↔у. 17.f1 = x → y, f2 = x ∨ y .
4.f1 = x ⊕ y, f2 = x ∨ y . 11. f1 =x⊕y, f2 =х∨y. 18.f1 =
x → y, f2 = x ∧ у.
5. f1 = x ∧ y, f2 = у. 12. .f1 = x⊕y, f2 =х ↔y. 19. .f1 = x ∨ y, f2 = x.
6.
f1 =
x ∨ y, f2 = х y. 13.f1 = x ↓ у, f2 = x →у. 20. f1 = x → y, f2 = x ∨ yz.
7.
f1 = x ⊕ y f2 = х ↔ yz. 14. f1 = x, f2 =(х∨y)(x∨y). 21. f1 = xy, f2 = х ∨ y .
4.4. Записать функции из задачи 1.4 (§1) в базисах S1={¬,∧,∨}, S2={¬,&}, S3={¬,∨}, S[1]={1,&,⊕}, S5={|}, S6={↓}.
4.5. Выяснить, является ли функция f самодвойственной; монотонной:
1)
f =
xy ∨ yz ∨ xz; 11)
f = x1x2x3 ⊕ x1x2x3 ⊕ x2x3 ⊕ x3x1;
2) f = х ⊕ у ⊕ z ⊕1; 12) f = x1 ⊕x2 ⊕(x1x2 ∨ x2x3 ∨ x3x1);
3)
f
= (x ∨ y ∨ z)t ∨ xyz; 13)
f =x1x2x3 ⊕x1x2 ⊕x2x3 ⊕x3x1;
4) f = x ⊕ у; 14) f = x1x2 ⊕ x2x3 ⊕ x1 ⊕ x ;3
5) f = х ∨ у; 15) f = x1x2 ⊕ x2x3 ⊕ x3x1 ⊕ x2 ⊕ x ;3
6)
f = (x ∨
y ∨ z)t ∨ xyz; 16) f =(x1 →x2)⊕(x2 →x3)⊕(x3 →x ).1
7)
f = x →
y; 17) f =
x1 ⊕ x2 ⊕(x1x2 ∨ x2x3 ∨ x3x1);
8) f = xy ∨ z; 18) f = x1x2 ⊕ x3( x1 ∨ x2 );
9)
f =
xy(x ↔ y);
19) f =
x1 ⊕ x2 ⊕( x1x2 ∨
x2x3 ∨
x3x1 );
|
10) f = (x ∨ y ∨ z)t ∨ xyz; |
20) f =(x1 →x2)⊕(x2 →x3)⊕(x3 →x1)⊕x3. |
|||
|
1) f = (1010 ); |
11) f = (1100 |
1001 0110 1100 ); |
|
|
|
2) f = (1001 ); |
12) f = (1000 |
0011 1000 1100 ); |
|
|
|
3) f = (1101 ); |
13) f = (1110 |
0111 0001 1000 ); |
|
|
|
4) f = (1011 ); |
14) f = (1100 |
0011 1010 0101 ); |
|
|
|
5) f = (1001 0110 ); |
15) f = (1001 |
0110 1001 0110 ); |
|
|
|
6) f = (1101 0111 ); |
16) f = (1010 |
0101 0101 1010 ); |
|
|
|
7) f = (0010 0110 ); |
17) f = (1001 1011 1011 1001 ); |
|
||
|
8) f = (0100 1101 ); |
18) f = (1101 0111 1011 0010 ); |
|
||
|
9) f = (0001 0111 ); |
19) f = (1101 0100 1011 0010 ); |
|
||
|
10) f = (0111 0001); |
20) f = (0011 0100 1011 0011 ). |
|
||
4.7. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g двойственной
|
к функции f: |
|
|
1) f = x ⊕ y , g = x ~ y ; |
2) f = x| y , g = x ↓ y; |
|
|
|
|
5) f = x⊕y⊕z, g = x⊕y⊕z; |
6) f = x⋅ y ∨ z , g = x⋅(y ∨ z); |
|
7) f = x⋅ y →z , g=x⋅y⋅z; |
8) f = xy ⊕ xz ⊕ yz, g = xy∨xz∨ yz; |
9) f = (x ∨ y ∨ z)⋅t ∨ x⋅ y ⋅ z , g = (x ∨ y ∨ z)⋅t ∨ x⋅ y ⋅ z ;
10) f = xy ∨ yz ∨ zt ∨ tx, g = xz ∨ yt ;
11) f = (x ∨ y)→ (z ⊕t), g = (x| y)⋅(z ~ t);
12)
f =(x→y) (⋅
z→t), g = (x → z)⋅(x → t)⋅(y → z)⋅(y → t).
13)
f = x ⋅1∨ y ⋅(z ∨ 0)∨
x ⋅
y ⋅
z , g = x⋅(y⊕z); 14)
f =
(x ↓ y)⊕
((x| y)↓
(x ~ y ⋅
z)),
g =
x ⋅
y ∨
x ⋅
y ∨
y⋅z ;
15) f = (x ∨ y ∨ (y ⋅ z ⊕1))↓
z , g=x∨y∨z .
|
2) f = x → y ⊕ xy; |
|
|
4.8. Представив функцию f полиномом, выяснить,
является ли она линейной:
|
1) f = x → y; |
|
|
|
3)
f =
xy(x ↔ y);
13) f =( xy ∨ x ⋅ y )z ∨
z( xy ∨
xy );
4)
f = xy ∨ xy ∨ z; 14)
f = x ⊕ ху ⊕⋅y ⋅ z ⊕ xyz;
5)
f = ((x → y)(y → x)) ↔ z; 15) f =( xyz ∨
xyz )⊕
x( y ⊕
z );
6) f = xyz ∨ xy; 16) f =( xyz ⊕ x( yz )⊕ x( y ∨ z );
7)
f = xyz ⊕
xyz ⊕
xy; 17)
f =
( xyz ⊕
xyz )∨( xyz ⊕
xyz );
8) f = (x ∨ y) ⊕ xyz; 18) f = (x ⋅ y ⋅ z ↔ xyz) ↔ (xyz ↔ xyz);
9) f = x ⊕ x ⋅ y ⋅ z ⊕ xyz; 19) f = (x ⋅ y ⋅ z ↔ xyz) ∨ (xyz → xyz);
10) f = ( x ∨ yz )⊕ xyz; 20) f = (xy ↓ x ⋅ y)z ∨ (xyz ↓ xy).
4.9.. Выяснить, являются ли линейными (монотонными) функциями, функции заданные векторно в задаче 4.6.
4.10.Выяснить, полна ли система функций:
|
1) A = {0, x1 ~ x2}; |
|
14) A = {0, x1 ∨ x 2 ,1}; |
|
2) A = {1,x1 ⊕ x2}; |
|
11) A = {0,1, x1 ⊕ x 2 ⊕ x 3}; |
|
3) A = {x1 ⊕1, x1 ⊕ x2}; |
|
12) A = {xy ⊕ yz ⊕ zt,0,1, x ∨ y} ; |
|
4) A = { x1 ⊕ x2 ,x1 ~ x2 }; |
|
13) A = {x 1 ⊕ x 2 ⊕ x 3 ⊕ 1, x 1 ~ x 2}; |
|
5) A = {x ⊕ y, x ~ yz}; |
|
14) A = {x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 , x1 ⊕ 1}; |
|
6) A ={x → y,x ⊕ y,x ∨ y}; |
|
15) A = { x 1 ⊕ x 2 ⊕ x 3 ⊕ 1,0}; |
|
7) A = {x ⊕ y ⊕ z,x ∨ y,0,1}; |
|
16) A = {x1 ⊕ x 2 , x1 ⊕ x 2 ⊕ x 3 ⊕ 1,1}; |
|
8) A ={x ⊕y⊕yz,x ⊕ y⊕1}; |
|
17) A ={x⊕y⊕z,x⊕y⊕z⊕1,xy⊕yz⊕zx,x}; |
|
9) A ={xy ∨ z,xy ⊕ z,xy ~ z}; |
|
18) A = {x ⊕ y ⊕ z,xy ⊕ zx ⊕ zy,0,1}; |
10)
A = {x1 ⊕ x 2 ⊕ x3, x ⊕ 1,0}; 20)
A =
{x1x 2 ∨ x1x 2 , x ⊕ 1}.
4.11. Выяснить, полна ли система А функций, заданных векторами своих значений:
1) A = { f1 = ( 0110 ), f2 = (11000011 ), f3 = (10010110 )};
2) A = { f1 = ( 0111 ), f2 = ( 01011010 ), f3 = ( 01111110 )};
3) A = { f1 = ( 0111 ), f 2 = (10010110 )};
4) A = { f1 = ( 0110 ), f2 = (11000011 ), f3 = (10010110 )};
5) A = { f1 = ( 1001 ), f 2 = ( 11101000 )};
6) A = { f1 = (11 ), f2 = ( 0111 ), f3 = ( 00110111 )};
7) A = { f1 = (10 ), f 2 = ( 00110111 )};
8) A = { f1 = (11 ), f 2 = ( 00 ), f3 = ( 00110101 )}; 9) A = { f1 = (10000001 ), f2 = ( 0111 ), f3 = (1011 )}; 10) A = { f1 = (10000001 ), f2 = ( 0110 ), f3 = (1001 )}.
Множество всех булевых в базисе S={¬, &, ∨} образуют булеву алгебру. Если х - логическая переменная, а σ∈{0,1} то выражение
σ ⎧x если σ = 1 σ ⎧1 если x = σ
x =
⎨
или x =
⎨ ,
⎩x если σ = 0 ⎩0 если x ≠ σ
называется литерой. Литеры x и ¬x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.
Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем:
1. используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;
2. 
применяем правило снятия двойного отрицания:
x=x;
3. далее следует использовать законы дистрибутивности, причем первый закон дистрибутивности для приведения к ДНФ, и второй закон дистрибутивности для приведения к КНФ.
Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).
Задача 1. По данной таблице истинности построить СДНФ.
Решение рассмотрим на примере функции f(x,y,z), заданной таблично (таб.5.1).
Таблица 5.1
|
x |
y |
z |
Конституенты 1 |
Конституенты 0 |
f(x,y,z) |
|
0 |
0 |
0 |
|
x∨y∨z |
0 |
|
0 |
0 |
1 |
|
|
1 |
|
0 |
1 |
0 |
|
|
1 |
|
0 |
1 |
1 |
|
|
0 |
|
1 |
0 |
0 |
|
|
0 |
|
1 |
0 |
1 |
|
|
1 |
|
1 |
1 |
0 |
|
|
1 |
|
1 |
1 |
1 |
x ⋅ y ⋅ z |
|
1 |
Конституенты_1 (или основные конъюнкции ), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные x,y,z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Правило для построения СДНФ: следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих конституент 1. Так для нашего примера, имеем
f(x,y,z)= x ⋅ y ⋅ z ∨
x ⋅
y ⋅
z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨
x ⋅
y ⋅
z .
Задача 2. По данной таблице истинности построить СКНФ.
Конституенты_0 для набора нулей и единиц (которые принимают переменные x,y,z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в дизъюнкцию входит ее отрицание. Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая
СКНФ. Так для нашего примера, имеем
f(x, y, z) = ( x ∨ y ∨ z ) ⋅ ( x ∨ y ∨ z ) ⋅ ( x ∨ y ∨ z ) .
Описанный способ нахождения СДНФ (СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ.
2. Если в некоторый конъюнкт К не входит скажем переменная у, то этот конъюнкт
заменяем на эквивалентную
формулу K&(y ∨
y) и, применяя 1-й
закон дистрибутивности, приводим полученную формулу к ДНФ. Если недостающих переменных
несколько, то для каждой из них к конъюнкту добавляем соответствующую
формулу вида (y ∨ y) .
3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
Замечание: Для построения СКНФ дизъюнкт не содержащий скажем переменную у
заменяем на эквивалентную
формулу D ∨
y⋅
y и, применяем 2-й
закон дистрибутивности.
Пример 5.1. Построить СКНФ для функции F при помощи эквивалентных преобразований
1 ⊕
z)
=
x ∨
(y ⊕ z) =
x ∨
(yz ∨ yz) =
x ∨
yz yz⋅ )
=
= x ∨ (y ∨ z)⋅(y ∨ z) = (x ∨ y ∨ z)⋅(x ∨ y ∨ z) − СКНФ.
Пример 5.2. С помощью эквивалентных преобразований приведите формулу к ДНФ,
КНФ, СДНФ, СКНФ. F = ((x ↓ y) → z) ↔ y .
Решение: Приведем функцию F к базису S1={┐,&,v}
F =(x⋅y →) ↔ y =(x⋅y∨z) ↔ y =(x∨
y∨z) ↔ y =(x∨
y∨z∨ y)(x∨ y∨z∨ y) =
= x⋅y⋅z∨ y = x⋅y⋅z⋅y =(x∨ y∨z)y−КНФ.
Для приведения F к ДНФ, применим первый закон дистрибутивности.
F = xy ∨ yy ∨ z ⋅ y = xy ∨ z ⋅ y = xy ∨ z ⋅ y –ДНФ.
Приведем функцию F к СДНФ:
F = xy ∨ zy = xy(z ∨ z) ∨ zy(x∨ x) = xyz ∨ xyz ∨ (zyx∨ zyx) = xyz ∨ xyz ∨ xyz.
Приведем функцию F к СКНФ:
F = (x ∨ y ∨ z)y = (x ∨
y ∨
z)(y ∨
xx) = (x ∨
y ∨
z)(y ∨
x)(y ∨
x) = (x ∨
y ∨
z)(y ∨
x ∨
zz)⋅
(y ∨ x ∨ zz) = (x ∨ y ∨ z)(y ∨ x ∨ z)(y ∨ x ∨ z)(y ∨ x ∨ z)(y ∨ x ∨z).
Пример 5.3. Привести функцию к ДНФ, используя 1-ый закон дистрибутивности.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y⋅z)⋅(y∨z)= -это КНФ
= (0 ∨
x ⋅ y ∨ x ⋅ y ⋅ z ) ⋅ ( y ∨ z ) = ( x ⋅ y ∨ x ⋅ y ⋅ z ) ⋅ ( y ∨ z ) = -это другая КНФ =
x ⋅
y ⋅
у ∨
x ⋅
y ⋅
z ⋅
y ∨
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z ⋅
z =
0 ∨
0 ∨
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z =
=
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z -это ДНФ.
Пример 5.4. Привести функцию к КНФ, используя второй закон дистрибутивности.
x ∨ y ⋅ 
x= x ∨ y ⋅ ( 
x= x ∨ y ⋅ ( 
x=
= x ∨ y ⋅ z ⋅ (x ∨ y ) = (x ∨ y ⋅ z ) ⋅ (x ∨ x ∨ y ) = (x ∨ y ) ⋅ (x ∨ z ) ⋅ (1 ∨ y ) = = ( x ∨ y ) ⋅ ( x ∨ z ) - это КНФ.
Пример 5.5. По данной таблице истинности (таб.5.1) построить СДНФ. Таблица 5.1
|
x |
y |
z |
основные конъюнкции |
f(x,y,z) |
|
0 |
0 |
0 |
x ⋅ y ⋅ z |
0 |
|
0 |
0 |
1 |
x ⋅ y ⋅ z |
1 |
|
0 |
1 |
0 |
x ⋅ y ⋅ z |
1 |
|
0 |
1 |
1 |
x ⋅ y ⋅ z |
0 |
|
1 |
0 |
0 |
x ⋅ y ⋅ z |
0 |
|
1 |
0 |
1 |
x ⋅ y ⋅ z |
1 |
|
1 |
1 |
0 |
x ⋅ y ⋅ z |
1 |
|
1 |
1 |
1 |
x ⋅ y ⋅ z |
1 |
Построим СКНФ для нашего примера на основании замечания.
1. 
Строим СДНФ для отрицания:
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z .
2. Используем законы де Моргана, получаем
f = f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z = x ⋅ y ⋅ z & x ⋅ y ⋅ z & x ⋅ y ⋅ z = = (x ∨ y ∨ z) ⋅ (x ∨ y ∨ z ) ⋅ (x ∨ y ∨ z) .
Пример 5.6. Построим сокращенную ДНФ исходя из СКНФ булевой функции f=(1111 0100 1010 1111). Решение:
f (x, y, z,t) =
(x ∨
y ∨
z ∨
t)(x ∨
y ∨
z ∨
t)(x ∨
y ∨
z ∨
t) &
Сокращенная ДНФ для функции: f(x,y,z,t) = xy∨xt∨xy∨ yt∨xzt∨ yzt.
5.1. Какие из следующих функций записаны в нормальной форме, а какие нет?
1)
x ∨ y → x, 2)(x
⋅ y ∨ x) ⋅(z ∨ x), 3)(x
∨ z ∨ x) ⋅ x ⋅ y ⋅ (z ∨ x),
4) x ⋅ y ∨ x ⋅ y ⋅(x ∨ y), 5) x ⋅ y⋅z⋅x ⋅x ∨ z⋅ y ∨ x , 6) (x∨y∨y∨z)⋅z⋅(z∨x),
7) x⋅y∨x⋅z∨y⋅z⋅x∨z, 8)
(x∨y∨z)(y∨xy∨z),
9) xyz ∨
xy ∨ xyz,
10) xyz ∨ xyz ∨ xyz, 11) (yz∨xy∨z)(x∨y∨xz), 12) xyz ∨ xy ∨ xyz,
13) xy∨ z∨ xy∨ z ∨ xy, 14)
(x∨y∨z∨t)(x∨y)t,
15) x∨y∨z∨(x∨yz),
16) xy∨xyz∨yz(x∨z),
17) x ∨
y ∨ z ∨ xy ∨ yz , 18)
xyz ∨ (x
∨ y)(y
∨ z),
19)(x∨y∨z)(x∨y∨z)(x∨y),
20) xyz∨xy∨zt∨xyzt, 21)
(x∨y∨z)⋅x⋅(z∨x).
5.2. Привести следующие формулы к ДНФ и КНФ и по возможности упростить.
1) x ∨ yz; 2) x ↔ y ; 3) x ↔ yz;
4) x ↔ y ↔ z; 5) xy ↔ xy; 6) x → (y → z);
7) xy ∨ (x
→ y);
8) xy ∨
yz ∨ z ; 9)
x ∨ yz ∨ xyz ;
10) x ∨ y ∨ z ⋅ x ∨ x ⋅ y ; 11) (x ⋅ y ∨ z)⋅(y ∨ x ⋅z); 12) (xyz∨x)⋅(x∨y∨z∨xz)∨y;
13) x ⋅ y⋅x ⋅ y ∨ xyz∨ z ; 14) x ⋅ y → z ∨ y; 15) z → y ∨ x ⋅ z ;
16) (x ⊕ y) → (z ⊕ x); 17)
(x ↓ y)
⊕ z ⋅ x ; 18)
(x ∨ z) → (y ↓ z); 19) (x |
y) → x ⋅ y ∨ z ; 20)
x ∨ y ↔ x ⊕ z ; 21) x ⋅ y ∨ xyz ∨ z .
5.3. Привести функции к совершенным формам (СДНФ и СКНФ) путем эквивалентных преобразований.
1.
xy ∨
xyz ∨
z. 2.
(x
∨ z)⋅(x
∨ y).
3. x ∨ y
∨ zx .
4. (x ∨ y ∨ z)⋅ y⋅(y ∨ z) . 5. x ⋅ y⋅z. 6. y∨ x⋅(yz∨ z).
7.
(xу∨ z)⋅х⋅(xz ∨ y) . 8.
xz ∨
y →
xz . 9.
(y ∨ z) ⊕ x ⋅ y⋅z .
10.
(x ↓ y)
∨ уz ∧ x. 11.
x ↔
x ⋅
y ∧
z . 12.
x ∧ y ↓ z.
|
13. x ∨ y. |
14. xy(x → y). |
|
|
16. x → yz . |
17. (x → y)→ x . |
18. xy → (y → x). |
|
19. x ∨ y → (x → z). |
20. xy → zt . |
|
5.4. Построить СДНФ и СКНФ для функций заданных вектором значений булевой функции.
1) (0011), 2) (0101), 3) (1110), 4) (1000), 5) (0011 1010),
6) (1100 0101), 7) (1000 1111), 8) (1110 1100), 9) (1000 0011), 10) (1100 0000);
11) (1101 0000 0011 0110), 12) (0000 1111 0101 1100); 13) (1001 0000 0011 0100); 14) (0101 0110 0010 0111); 15) (0001 1100 0011 1110); 16) (1101 1111 0011 0001), 17) (1111 0000 1111 0110); 18) (0101 0110 0101 0110); 19) (1000 0110 1011 1111); 20) (1010 1111 0111 0000).
5.5. Доказать равносильности путем приведения к СДНФ или СКНФ:
|
|
|
15) (x → y)→ y ≡ x ∨ y ; |
|
2) x(x ∨ y) ≡ x ; |
|
16) x → (y → z) ≡ x & y → z ; |
3) x ∨ xxy ≡ x ∨ y; 10) x ∨ xy ≡ x; 17) (x → z)(y → z) ≡ (x ∨ y)→ z ;
4)
x ∨
y ≡ x ⋅ y ; 11) x ∨ xy ≡ x ∨ y ; 18) x(y
∨ z)
= (x
∧ y)∨ (x
∧ z);
5)
x → y ≡ xy ; 12)
x(x
∨ y)≡ xy ; 19) x ↔ y ≡ (x
→ y)∧ (y
→ z);
|
6) (x ∨ y)(x ∨ y) ≡ x ; |
|
|
7) x ↔ y ≡ y ↔ x ; |
14) x ∨ (x & y) ≡ x ∨ y ; |
5.6. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ.
1.
xy . 8. z → x ↔ (x | y).
15. x↓y→ х ∨ у ↔ x|y.
2.
x ⊕
y . 9. ((x|
y) → z)
⊕ y. 16. (x ∨ y) → (z ⊕ x).
3. x ↔ y . 10. (x ∨ y) → (z ⊕ x). 17. (z → x) ↔ (y | x).
4. x ↓ y. 11. (x | y) ⊕ (z → x). 18.((x ↓ y) → z) ⊕ y.
5. x → y . 12. (z → x) ⊕ (x | y). 19. x↓y→x|y⊕x.
6. x → yz. 13. (x ∨ y) → (z ⊕ x). 20. (x ∨ y) → (z ↔ x).
7. xyz. 14. ((x ↓ y)⊕ z) → yx.
5.7. Проверьте двумя способами, будут ли эквивалентны следующие функции. 1) составлением таблиц истинности; 2)приведением к СДНФ или СКНФ с помощью эквивалентных преобразований.
|
1. x ∨ y,x → y. |
|
11.x ∧ (y ↔ z), (x ∧ y) ↔ (x ∧ z). |
|
2. x → y,x ↔ y . |
|
12. x ∨ (y | z), (x ∨ y) | (x ∨ z). |
|
3. x ∨ y,x ⊕ y. |
|
13. x ⊕ (y → z), (x → y) ↔ (x ↓ z). |
|
4. xy ∨ z, x(y ∨ z). |
|
14. x → (y ⊕ z), (x → y) ⊕ (x → z). |
|
5.(x → y)z, x → yz . |
|
15. x |(y → z), (x | y) → (x | z). |
|
6. xy ↔ x,(x ↔ y)z . |
|
16. x ∧ (y → z), (x ∧ y) → (x ∧ z). |
|
|
|
17. x ∨ (y → z), (x ∨ y) → (x ∨ z). 18. x ⊕(y → z), (xy) ↔ (x ⊕ z). |
9. x ∨ (y → z), (x ∨ y) → (x ∨ z). 19. x ↓ (y ↔ z), (x ↓ y) ↔ (x ↓ z).
10. x ∧ (y → z), (x ∧ y) → (x ∧ z). 20. x ∧ (y ⊕ z), (x ∧ y) ⊕ (x ∧ z).
5.8. Построить совершенные формы (СДНФ и СКНФ) для булевых функций из задачи 5.2.
5.9. Используя дистрибутивный закон x⋅(y ∨ z) = x⋅ y ∨ x⋅ z и эквивалентности x ⋅ x = x,
x⋅x=0,А⋅0 = 0, А∨0 = А и А∨А⋅В = А перейти от заданной
КНФ функции f(x) к ДНФ:
1) f ( ~x 3 ) = ( x1 ∨ x2 )⋅( x1 ∨ x3 )⋅( x2 ∨ x3 );
2)
f ( ~x3 ) = x1 ⋅( x1 ∨
x2 ∨
x3 )⋅( x2 ∨
x3 );
3) f ( ~x3 ) = ( x1 ∨ x2 ∨ x3 )⋅( x1 ∨ x2 ∨ x3 )⋅( x1 ∨ x2 ∨ x3 );
4) f(~x3) = (x1 ∨ x3)⋅(x2 ∨ x3)⋅(x1 ∨ x2 ∨ x3);
5)
f(~x3) = (х1 ∨ x2
∨
x3)⋅(x1 ∨ x2 ∨ x3)⋅(х1 ∨ x2 ∨ х3);
6) f ( ~x3 ) = ( x1 ∨ x2 )⋅( x1 ∨ x3 )⋅( x1 ∨ x2 ∨ x3 );
7)
f(~x3 )=( x1 ∨
x2 )⋅( x1 ∨
x3 )⋅( x1 ∨
x3 )⋅( x2 ∨
x3 );
8) f ( ~x3 ) = ( x1 ∨ x2 ∨ x3 )⋅( x1 ∨ x2 ∨ x3 )⋅( x1 ∨ x2 ∨ x3 );
9)
f(~x4) = (x1 ∨ x2)⋅(x2 ∨ x3)⋅(x2 ∨ x4)⋅(x3 ∨ x4);
10) f ( ~x 4 ) = ( x1 ∨ x2 ∨ x3 ∨ x4 )⋅( x1 ∨ x2 ∨ x3 )⋅( x1 ∨ x4 ).
Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ (КНФ), представляющую эту функцию и имеющую наименьшее число вхождений переменных.
А) Карты Карно. Карты Карно для функций n переменных, представляет собой n прямоугольник, разделенный на 2 клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой.
Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной
Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила:
1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. m
2 , где m=0,1,2,...
m
2. Каждая клетка, входящая в группу из 2 клеток, должна иметь m соседних в группе.
3. Каждая клетка должна входить хотя бы в одну группу.
4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе.
5. Число групп должно быть минимальным.
Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.
Приведем шаблоны для n=3, которые помогают строить покрытия единицы (1).
Приведем шаблоны для n=4, которые помогают строить покрытия единицы (1).
Б) Метод Квайна. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза (либо сама либо ее отрицание). Формула f1 называется импликантой формулы f, если f1 — элементарное произведение и f 1 ∧ f = f 1 . Импликанта f1 формулы f называется простой, если после отбрасывания любой литеры из f1 не получается формула, являющаяся импликантой формулы f.
Сокращенной ДНФ называется дизъюнкция всех простых импликант данной формулы (функции). Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МДНФ).
Определим следующие три операции:
1) операция полного склеивания:
f ⋅ x ∨ f ⋅ x = f ⋅ ( x ∨
x ) = f ;
2) операция неполного склеивания:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3) операция элементарного поглощения: f ⋅ x σ ∨ f = f , σ ∈ {0,1} .
Теорема Квайна. Если исходя из СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.
На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие ни в одном склеивании.
Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.
Замечание. Для построения минимальной КНФ функции f, достаточно построить
минимальную ДНФ для функции f , а затем использовать f = f и законы де Моргана.
Пример 6.1. С помощью Карт Карно, построить МДНФ и МКНФ функций заданных вектором своих значений.
1) f(x,y,z)=(1011 0101); 2) f(x1,x2,x3,x4)=(1011 1111 1011 1100).
Решение. 1) Занесем данные в карту Карно. Удобно сначала отметить клетки, где функция равна нулю. Функция f равна нулю на наборах, являющимся двоичными разложениями чисел 1,4,6 (т.к. отсчет начинается с О). Таким образом, f(0,0,1)=f(1,0,0)=f(1,1,0)=0.
f = xz ∨ xy ∨ xz − min ДНФ.
Для построения МКНФ, построим МДНФ для функции f :
Переходя к функции f, получим:
f = f = xz ∨ xyz =(x ∨ z)(x ∨ y ∨ z)–МКНФ.
2) Заносим данные в карту Карно. Получаем, чтоf(0,0,0,1)=f(1,0,0,1)=f(1,1,1,0)=f(1,1,1,1)=0.
f = x2 x3 ∨ x1x3 ∨ x3 x4 ∨ x2x3 –МДНФ.
Для построения МКНФ Функции f, построим сначала МДНФ, функции f :
f = x1x2x3 ∨ x2x3x4 - МДНФ
Используя правила де Моргана, получаем:
f = f = x1x2x3 ∨ x2 ⋅ x3 ⋅ x4 = (x1 ∨ x2 ∨ x3)(x2 ∨ x3 ∨ x4)–МКНФ.
Пример 6.2. Пусть функция f{x,y,z) задана совершенной ДНФ
f =
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z ∨
x ⋅
y ⋅
z .
Производя операции склеивания, а затем элементарногопоглощения, имеем
f = x ⋅ y ⋅(z ∨
z) ∨ y ⋅ z ⋅(x ∨
x) ∨ x⋅ z ⋅(y ∨
y) = x ⋅ y ∨ y ⋅ z ∨ x⋅ z .
Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.
Для примера 6.2. матрица Квайна имеет вид
|
импликанты |
x ⋅ y⋅ z |
|
x ⋅ y⋅z |
x ⋅ y⋅z |
|
|
* |
* |
|
|
|
y⋅z |
|
* |
* |
|
|
x ⋅ z |
|
|
* |
* |
В тупиковой ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т. е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, которая имеет наименьшее число вхождений переменных.
В примере
6.2. по матрице Квайна находим, что минимальная ДНФ заданной функции есть x ⋅ y ∨ x ⋅ z .
Пример 6.3. Пусть функция f(x,y,z) задана совершенной ДНФ
f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z .
Производя в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, получим:
f = x ⋅ y ⋅(z ∨
z)∨ y ⋅ z ⋅(x ∨
x) ∨ y ⋅ z ⋅(x ∨
x)∨ x⋅ z ⋅(y ∨
y)∨ x⋅ y ⋅(z ∨
z)∨
∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z =
= x ∨ y ⋅ z ∨ x ⋅ z ∨ x ⋅ y ∨
∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z =
= y ⋅ ( x ∨ x ) ∨ y ⋅ ( z ∨ z ) ∨ x ⋅ y ∨ y ⋅ z ∨ y ⋅ z ∨ x ⋅ z ∨ x ⋅ y ∨
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z =
= y ∨ x ⋅ y ∨ y ⋅ z ∨ y ⋅ z ∨ x ⋅ z ∨ x ⋅ y ∨
∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z = y ∨ x ⋅ z .
Пример 6.4. Построить минимальную ДНФ для функции f (х1,х2.х3,х4) с вектором значений (1110 0101 0100 1101).
Занесем данные в карту Карно и произведем склеивание 1. Склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания. Следовательно. минимальная ДНФ имеет вид
x1 x 2 x 4 ∨ x1 x 2 x3 ∨ x3 x4 ∨ x2x4 ∨ x1x2 x3 .
6.1. Построить минимальные ДНФ и КНФ, используя карты Карно.
1) z 2) z 3) z 4) z
|
|
|
1 |
|
|
|
|
1 |
1 |
|
1 |
1 |
|
|
|
|
1 |
1 |
1 |
|
1 |
1 |
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
1 |
|
1 |
|
5). |
|
|
z |
6) |
|
z |
7) |
z |
8) |
|
|
|
z |
x 1 x
1 x x
|
|
1 |
1 |
1 |
|
|
1 |
|
|
|
1 |
1 |
1 |
|
|
1 |
1 |
1 |
|
|
1 |
|
|
1 |
|
|
1 |
1 |
|
|
|
|
1 |
|
|
|
1 |
|
|
x 1 x
1 x
x
9) X3 10) X3 11) X3 12) X3
|
|
1 |
1 |
1 |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
|
|
1 |
|
1 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
|
1 |
|
|
1 |
|
1 |
1 |
|
1 |
|
1 |
|
|
1 |
|
|
|
|
|
|
1 |
1 |
|
1 |
|
|
1 |
|
1 |
|
|
1 |
1 |
|
|
|
1 |
1 |
|
|
|
|
1 |
1 |
X1 X1
X1X1
X2
13) X3 14) X3 15) X3 16) X3
|
|
1 |
1 |
1 |
|
|
|
1 |
1 |
|
|
1 |
|
1 |
|
1 |
|
|
1 |
|
1 |
1 |
|
|
|
|
|
1 |
1 |
|
|
1 |
1 |
1 |
|
1 |
1 |
|
|
|
1 |
1 |
|
1 |
|
1 |
1 |
|
|
|
|
1 |
|
|
|
|
|
1 |
1 |
|
|
|
1 |
|
|
|
1 |
1 |
1 |
|
|
1 |
1 |
1 |
|
|
1 |
1 |
|
X1 X1
X1X1
X2
6.2. Построить минимальные ДНФ и КНФ, используя карты Карно и метод Квайна, если функции а)f(x,y,z) и б)f(x1,x2,x3,x4) заданны вектором своих значений
1) а) (1000 1111); б) (1100 1101 0011 0011);
2) а) (1010 0101); б) (1111 1100 1011 1011);
3) а) (0011 1100); б) (1101 0011 1101 0011);
4) а) (1100 0101); б) (1110 0101 0011 0101);
5) а) (1011 1100); б) (1100 1011 1111 1011);
6) а) (0101 0011); б) (0101 0101 1110 0011);
7) а) (1111 1011); б) (0011 0011 1101 1101);
8) а) (0101 1001); б) (1011 1011 1100 1111);
9) а) (0011 1101); б) (0101 0011 0101 1110);
10) а) (1110 0011); б) (0011 1101 0011 1100);
11) а) (0010 0011); б) (0111 0010 1011 1111);
12) а) (1000 0011); б) (0000 1111 0101 1100);
13) а) (1100 0010); б) (1111 0111 0101 1101); 14) а) (1110 0101); б) (0101 1101 0101 0000);
15) а) (0000 1111); б) (0110 0011 0101 1110);
16) а) (1100 1011); б) (1010 1010 1001 1100);
17) а) (0000 1011); б) (1100 0011 0011 1010);
18) а) (1011 1011); б) (1111 1111 0101 0100); 19) а) (1111 0001); б) (1000 0011 1111 0000); 20) а) (1000 0000); б) (0000 0000 0101 1101).
6.3. Построить минимальные ДНФ, используя метод Квайна.
1) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ,
2) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
3) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ;
4) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ; 5) f = x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z .
6) f = x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ,
7) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ;
8) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ;
9) f = x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ;
10) f = x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ;
11) f = x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ;
12) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ;
13)
f = x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ; 14) f = x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y⋅ z ∨ x ⋅ y ⋅ z;
15) f = x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ;
16) f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ;
17) f = x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ;
18) f = x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ;
G
19) f = x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z;
20) f = x⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x⋅ y ⋅ z ∨ x⋅ y ⋅ z.
6.4. Построить минимальную ДНФ, КНФ методом Квайна если:
1. f(1,0,0)= f(1,1,0)= f(1,0,1)= f(1,1,1)= f(0,0,0)=1.
2. f(1,1,1)= f(1,1,0)= f(1,0,1)= f(0,0,0)=1.
3. f(1,1,0)= f(1,0,1)= f(0,1,1)= f(1,0,0)=1.
4. f(1,0,0)= f(1,1,1)= f(1,0,1)=1.
5. f(1,0,1)= f(1,1,0)= f(0,0,1)= f(1,1,1)= f(0,0,0)= f(1,0,0)=1.
6. f(1,1,1)= f(1,1,0)= f(1,0,1)= f(0,0,1)= f(0,0,0)=1.
7. f(1,0,0)= f(1,1,0)= f(0,0,0)=1.
8. f(1,0,0)= f(1,0,1)= f(1,1,1)=1.
9. f(1,1,0)= f(1,0,1)= f(1,1,1)= f(0,0,1)=1.
10. f(1,1,1)= f(1,1,0)= f(1,0,1)= f(0,1,1)= f(0,0,0)= f(0,1,0)= f(0,0,0)=1.
11. f(1,0,0,1)= f(1,0,0, 0)= f(1,0,1,0)= f(1, 1,0, 1)= f(1,1,0,0)=1.
12. f(1,0,0, 0)= f(1,0,1,0)= f(1, 1,0, 1)= f(1,1,0,0)=1.
13. f(0,0,0,1)= f(1,0,0, 0)= f(1,0,1,0)= f(1, 1,0, 1)= f(1,1,0,0)=1.
14. f(1,0,0, 0)= f(1,0,1,0)= f(1, 1,0, 1)= f(1,1,0,0)=1.
15. f(1,0,0,1)= f(1,0,0, 0)= f(1,0,1,0)= f(1, 1,0, 1)= f(1,1,0,0)= f(1,1,0,0)= =f(0,1,0,1)=f(1,1,1,1)=1.
16. f(1,0,0, 0)= f(1,0,1,0)= f(1, 1,0, 0)= f(1,1,0,1)=1.
17. f(1,0,0,1)= f(1, 1,0, 1)= f(1,1,0,0)= f(1,0,0, 0)= f(1,0,1,0)= f(0, 1,0, 1)= =f(1,0,0,0)=1.
18. f(0,0,0,1)= f(1,0,0, 0)= f(0,0,1,0)= f(1,0,0, 1)= f(0,1,0,0)=1.
19. f(1,0,0, 0)= f(1, 1,0, 0)= f(1,1,1,0)= f(1,0,0, 1)= f(1,0,1,0)= f(1, 1,0, 1)= =f(0,1,0,0)=1.
20. f(1,1,1,1)= f(1,1,0, 0,)= f(1,0,1,0)= f(1, 1,0, 1)= f(0,1,0,0)=1.
6.5. Построить сокращенную ДНФ по заданной КНФ:
1)
(x1 ∨ x2 ∨ x3)(x1 ∨ x2 ∨ x3)(x2 ∨ x3);
2) (x1 ∨ x2)(x1 ∨ x2 ∨ x3);
3) (x1 ∨ x2 ∨ x3)(x1 ∨ x2)(x1 ∨ x2 ∨ x3);
4)
(x1 ∨
x2 ∨
x3)(x1 ∨
x2 ∨
x3);
5) (x1 ∨ x2)(x2 ∨ x3)(x3 ∨ x1);
6)
(x1 ∨
x2)(x2 ∨
x3)(x3 ∨
x4)(x4 ∨
x1);
7)
(x1 ∨ x2)(x1 ∨ x2 ∨ x3)(х2 ∨ х3);
8)
(x1 ∨ x2 ∨ x3)(x2 ∨ x3)(x2 ∨ x3);
9)
(x1 ∨
x2 ∨
x3)(x1 ∨
x2 ∨
x4)(x2 ∨
x2 ∨
x4);
10)
(x2 ∨ x3)(x1 ∨ x2)(x1 ∨ x3)(x1 ∨ x2)(x2 ∨ x3).
Множество булевых функций, заданных в базисе Жегалкина S={⊕,&,1} называется алгеброй Жегалкина. Основные свойства.
1. .коммутативность H1⊕H2=H2⊕H1, H1&H2=H2&H1;
2. ассоциативность H1⊕(H2⊕H3)=(H1⊕H2)⊕H3, H1&(H2&H3)=(H1&H2)&H3;
3. дистрибутивность H1&(H2⊕H3)=(H1&H2)⊕(H1&H3);
4. свойства констант H&1=H, H&0=0, H⊕0=H;
5. H⊕H=0, H&H=H.
Утверждение 7.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции:
x =1⊕x, x∨y=x⊕y⊕xy, x∼y=1⊕x⊕y, x→y=1⊕x⊕xy, x↓y=1⊕x⊕y⊕xy, x|y=1⊕xy.
Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x1,x2,…,xn называется выражение вида
P(x1,x2,…,xn)=c0⊕с1x1⊕c2x2⊕…⊕cnxn⊕c12x1x2⊕…⊕c12…nx1x2…xn, где постоянные ск могут принимать значения 0 или 1.
Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).
Теорема 7.1. Каждая булева функция представляется единственным образом в виде полинома Жегалкина.
Основные методы построения полиномов Жегалкина:
1. Метод, основанный на преобразовании формул. Используя утверждение 7.1. приводим формулу к виду содержащему связки из базиса S={⊕,&,1}; раскрываем скобки используя закон дистрибутивности (см. свойство 3); а затем применяем свойства 4 и 5.
2. Метод неопределенных коэффициентов. Полином Жегалкина, реализующий заданную функцию f(x1,x2,…,xn) ищем в виде
P(x1,x2,…,xn)=c0⊕с1x1⊕c2x2⊕…⊕cnxn⊕c12x1x2⊕…⊕c12…nx1x2…xn.
Найдем коэффициенты ск. Для этого последовательно придадим переменным x1,x2,…,xn n значения из каждой строки таблицы истинности. В итоге получим систему из 2 уравнений с n
2 неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(x1,x2,…,xn).
Пример 7.1. Построить полином Жегалкина функции
a) f(x,y)=x→y, б) f (х, у,z) = ((x ↓ y) → z) ↔ y.
Решение. а) 1 способ. Запишем искомый полином в виде P(х,у)= c0⊕с1x⊕c2y⊕c12xy
Пользуясь таблицей истинности
|
x |
0 |
0 |
1 |
1 |
|
y |
0 |
1 |
0 |
1 |
|
x→y |
1 |
1 |
0 |
1 |
получаем, что f(0,0)=P(0,0)= c0=1, f(0,1)=P(0,1)= c0⊕ c2=1, f(1,0)=P(1,0)= c0⊕ c1=0, f(1,1)=P(1,1)= c0⊕с1⊕c2⊕c12=1.
Откуда последовательно находим, c0=1, с1=1, c2=0, c12=1. Следовательно, P(x, y) = 1⊕ х ⊕ xy.
2 способ (метод преобразования формул.) Имеем
x → y =
x ∨ y
= x ⋅ y = ( x ⋅( y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
б) 1 способ. Пусть полином Жегалкина имеет вид:
P(x1y1z) = c0 ⊕ c1x ⊕ c2y ⊕ c3z ⊕ c12xy ⊕ c13xz ⊕ c23yz ⊕ c123xyz.
P(0,0,0)=C0=1 (т.к. f(0,0,0)=1).
P(0,0,1)=C0 ⊕C3=0 (т.к. f(0,0,1)=0)⇒1⊕ c3 = 0 ⇒ c3 =1.
P(0,1,0)=C0 ⊕C2=0 ⇒1⊕ c2 = 0 ⇒ c2 =1.
P(1,0,0)=C0 ⊕C1=1 ⇒1⊕ c1 =1⇒ c1 = 0.
P(0,1,1)=C0 ⊕C2 ⊕С3 ⊕С23=0 ⇒1⊕1⊕1⊕ c23 = 0 ⇒1⊕ c23 = 0 ⇒ c23 =1.
P(1,0,1)=C0 ⊕C1 ⊕С3 ⊕С13=1 ⇒1⊕ 0 ⊕1⊕ c13 =1⇒ 0 ⊕ c13 =1⇒ c13 =1.
P(1,1,0)=C0 ⊕C1 ⊕С2 ⊕С12=0 ⇒1⊕ 0 ⊕1⊕ c12 = 0 ⇒ c12 = 0.
P(1,1,1)=C0 ⊕C1 ⊕С2 ⊕С3 ⊕С12 ⊕С13 ⊕С23 ⊕С123=0⇒
⇒1⊕ 0 ⊕1⊕1⊕ 0 ⊕1⊕1⊕ c123 = 0⇒1⊕ c123 = 0⇒ c123 =1.
Итак, получаем полином Жегалкина 3-й степени. P(x, y,z) =1⊕ y ⊕ z ⊕ xy ⊕ yz ⊕ xyz .
Пример 7.2.. Построить полином Жегалкина для функции f=(1011) методом неопределенных коэффициентов. Является ли f линейной.
Решение. Ищем полином Жегалкина P(x,y) в виде:
P(x, y) = c0 ⊕ c1 ⊕ c2y ⊕ c3xy.
Используя таблицу истинности для f2, полученную в п.3, имеем
P(0,0)=C0=1 ⇒ C0=1,
P(0,1)=C0 ⊕C2=0 ⇒ 1⊕C2=0 ⇒ C2=1, P(1,0)=C0 ⊕C1=1 ⇒ 1⊕C1=1 ⇒ C1=0,
P(1,1)=C0 ⊕C1 ⊕C2 ⊕C3=1 ⇒ 1⊕0⊕1⊕C3=1 ⇒ C3=1. Итак, f=1⊕y⊕xy – не линейна.
7.1. Построить полином Жигалкина, используя эквивалентные преобразования.
1. x ↔ y . 8. (x → y)(y → z). 15. x y→ х ∨ у ↔ x.
2.
x → y . 9. (xy
∨ xy)⊕ z .
3. xy ↓ z . 10. x ↓ yz. .
4.
(x
∨ y)z
. 11. (x → y)(y → x).
18. (x
∨ y)
→ zy .
5.
xy z . 12.
x ∨ y ∨ z . 19.
(x
↔ y)
↓ (x
⊕ x ⋅ z).
6.
xy(x
⊕ y).
13. x ⊕
y ↓ z. 20.
(xz
↔ xyz)∨ (xy
→ ⋅z).
7.
xyz ∨ xy . 14.
x ∨ yz ∨ xyz .
7.2. Постройте полином Жегалкина методом неопределенных коэффициентов.
1.
(x
↔ y)
↔ z . 8.
xy ∨ yz ∨ zt ∨ tx . 15.
(z → x)
⊕ (x | y).
2.
x
→ (y
→ z).
9. x↓y→ х ∨ у ↔ x|y. 16. (x ∨ y) → (z ⊕ x). 3. (x
y)↓ z . 10. x↓y→x|y⊕x. 17. (x
∨ y) → (z ⊕ x).
4.
xy(x
⊕ y).
11. z →
x ↔ (x
| y). 18. (z →
x) ↔ (y
| x).
5. xyz ∨ xyz ∨ xyz . 12. ((x| y) → z) ⊕ y. 19. ((x↓ y) → z) ⊕ y.
6.
(x
→ y)(y
↓ z).
13. (x ∨ y)
→ (z ⊕ x). 20.
(x ∨ y)
→ (z ↔ x).
7.
(x
→ y)∨ z)x
. 14. (x | y) ⊕
(z → x).
7.3. Постройте полином Жегалкина, если функции f(x,y,z) и f(x1,x2,x3,x4) заданны вектором своих значений
1) (1010 0101); 11) (1111 1100 1011 1001); 2) (0011 1101); 12) (1101 0011 1101 0011); 3) (0011 1100); 13) (1100 1011 1111 1011);
4) (0101 0011); 14) (0101 0101 1110 0011);
5) (0010 0011); 15) (0000 1111 0101 1100);
6) (0101 1001); 16) (0011 1101 0011 1100);
7) (1111 0101); 17) (1111 1100 1011 1011); 8) (0111 1111); 18) (0101 1111 1101 0011);
9) (1101 1011); 19) (0000 1011 1011 1010); 10) (0010 0011); 20) (0001 1101 1010 1111).
Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно ( И или 1) или ложно ( Л или 0) в конкретный момент времени.
При помощи связок «не», «и», «или», «если,… то», «если и только если» (им отвечают операции «¬», «&», «∨», «→», «∼» соответственно) можно построить более сложные высказывания (предложения). Для упрощения записи сложных высказываний вводится старшинство связок: «¬», «&», «∨», «→», «∼», что помогает опустить лишние скобки.
Простые высказывания назовем пропозициональными переменными.
Формула, принимающая значение И при всех значениях пропозициональных переменных называется тавтологией (или общезначимой), а формула, принимающая значение Л при всех значениях пропозициональных переменных называется противоречием (или невыполнимой).
Пример 8.1. После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:
а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;
б) если поедут Арбузов и Вишневский, то поедет и Брюквин.
Требуется установить, кто из перечисленных сотрудников войдет в состав экспедиции.
Решение. Назначение в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно.
Тогда условие а) можно записать в виде А→Б∨В, а условие б) в виде А&В→ Б.
Так как оба условия должны выполняться одновременно, то они должны быть соединены логической связью «и». Поэтому принятое решение можно записать в виде формулы
L=(А→Б∨В)&(А&В→Б) эта формула должна быть истинной.
Подвергнем формулу L равносильным преобразованиям, получим:
L=( А ∨Б∨B)&(A & B∨В)=( А ∨Б∨B)&( А ∨ В ∨Б).
Применяя к последнему выражению второй закон дистрибутивности, получим
L= А ∨[(Б∨В)&(Б∨ В )] = А ∨[Б∨(B&В )] = А ∨Б=A→Б.
Отсюда следует, что если поедет в экспедицию Арбузов, то с ним должен ехать и Брюквин.
Пример 8.2. Жили четыре друга. Звали их Альберт, Карл, Дитрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковыми, кроме того, фамилия Дитриха не Альберт. Определите фамилию и имя каждого мальчика, если дано, что имя мальчика, у которого фамилия Фридрих, есть фамилия того мальчика, имя которого фамилия Карла.
Решение. Будем обозначать имя и фамилию каждого мальчика двумя буквами в виде Ху, где «X» - первая буква имени, а «у» - первая буква фамилии. Из условия задачи следует, что нет мальчиков, соответствующих символам Аа, Дд, Кк, Фф, Да, то есть высказывания Аа=Дд=Кк=Фф=Да=0.
Но есть мальчик Ху такой, что есть мальчики Уф, Кх. Следовательно, истинной является формула Кх&Ху&Уф=1.
Но Х≠К, так как Кк=0; Х≠Ф, так как иначе будет два мальчика с фамилией Ф. Аналогично,
У≠К, У≠Ф. Следовательно, или X=Д, или Х=А. Но X≠Д, так как при Х=Д, У=А и, значит, Ху =Да, что противоречит условию. Значит, Х=А, а У=Д. Поэтому истинной является формула Ка&Ад&Дф&Фк. Следовательно, мальчики с именами Карл, Альберт, Дитрих и Фридрих имеют фамилии соответственно Альберт, Дитрих, Фридрих и Карл.
Пример
8.3. Докажем, что (B →
A) → ((B → A) → B) – тавтология.
(B →
A) → ((B → A) → B) = B∨ A ∨ B∨ A ∨ B =
= B&A ∨ B&A ∨ B = B&(A ∨ A) ∨ B = B ∨ B =1.
8.1. Какие из следующих предложений являются высказываниями:
а)
Москва–столица России; б) студент университета; в) 3 + 2 7 − 28; г) Луна есть
спутник Марса; д) а>0; е) Луна есть спутник Земли; ж) число
2 является корнем алгебраического уравнения 2x3 − 3x2 +1 = 0; з) уравнение
x3 + x2 − x +1 = 0 имеет своими корнями
множество чисел {1;-1;2}.
8.2. Среди следующих высказываний укажите элементарные и сложные. В сложных высказываниях выделить грамматические связки:
1) 
число 27 не делится на 3; 2)
число 15 делится на 5 и 3; 3) если число 126 делится на 9, то оно делится
на 3; 4) число 7 является делителем числа 42; 5) число 1269 делится
на 9 тогда и только тогда, когда 18 делится на 9; 6) 45 кратно 3 и 42 кратно
3; 7) 45 кратно 3 и 12 не кратно 3; 8) 25 =5 или 25 =-5; 9)
2≤5; 10) Если
число 212 делится на 3 и 4, то оно делится на 12; 11) Число 212 – трехзначное
и кратно 3 и 4, 12) Число 999 – трехзначное и кратно 3 и 111.
8.3. Какие из следующих высказываний истинны:
а) если 2х2=4, то 2<3; б) если 2х2=4, то 2>3; в) если 2х2=5, то 2<3; г) если 2х2=5, то 2>3.
8.4. Пусть p и q обозначают высказывания: p={Я учусь в школе}, q ={Я люблю математику}. Прочтите следующие сложные высказывания:
а) р ; б) р ; в) p&q; г) р&q ; д) р &q; е) р &q ; ж) p & q .
8.5. На вопрос, кто из трех учащихся изучал немецкий язык, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй. Кто из учащихся изучал немецкий язык?
8.6. По мишени произведено три выстрела. Рассмотрим высказывания рk – мишень поражена k-м выстрелом», k =1,2,3.Что означают следующие высказывания: а) p1∨р2∨р3; б) р1 ∧р2∧р3;
в) ( р1 ∨ р2 )∧р3?
Какие из этих трех высказываний истинны, если истинно р3, а р1 и р2 – ложны?
8.7. Пытаясь вспомнить победителей прошлого турнира, пятеро заявили, что, по их мнению:
1. Антон был вторым, Борис пятым.
2. Виктор был вторым, Денис третьим.
3. Антон был третьим, Евгений шестым.
4. Григорий был первым, Борис третьим.
5. Виктор был третьим, Евгений четвертым.
Впоследствии выяснилось, что каждый из высказавших свое мнение, ошибся один раз. Каково было истинное распределение мест в турнире, если никакие два участника турнира не делили одно место.
Ответ: I − Григорий, II − Виктор, III − Антон, IV − Евгений, V − Борис.
8.8. На вопрос: «Кто из трех учащихся изучал математическую логику?» получен верный ответ,- «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал математическую логику? Ответ: Второй ученик.
8.9. Определите, кто из четырех учеников сдал экзамен, если известно:
1. Если первый сдал, то и второй сдал.
2. Если второй сдал, то третий сдал или первый не сдал.
3. Если четвертый не сдал, то первый сдал, а третий не сдал.
4. Если четвертый сдал, то и первый сдал. Ответ: Экзамен сдали все.
8.10. Семья, состоящая из отца О, матери М и трех дочерей А,С,Д купила телевизор. Условились, что в первый-вечер будут смотреть передачи в таком порядке; 1) Когда отец О смотрит передачу, то мать М делает тоже.
2) Дочери С и Д, обе или одна из них, смотрят передачу.
3) Из двух членов семьи − мать М и дочь А – смотрят передачу одна и только одна.
4) Дочери А и С или обе смотрят, или обе не смотрят.
5) Если дочь Д смотрит передачу, то отец О и дочь С делают то же.
Кто из членов семьи в этот вечер смотрит передачу? Ответ: Передачу смотрят дочери А и С.
8.11. Определить, является ли каждая из следующих форм тавтологией, противоречием или не является ни тем, ни другим:
1) A≡(A∨A);
2) (A→B)→ ((B→C)→ (A→C));
3) ((A→B)&B)) → A;
4) (А )→ (A&B);
5) A&( ( A ∨ B ) );
6)
(A→B)≡(( A )∨B);
7) (A→B)≡((A&(B)) ;
8) A → (B → A) ;
9) (A → B) → ((B → C) → (A → C)) ;
10) (A& B) → A,(A& B) → B;
11) A → (B → (A& B));
12) A → (A ∨ B),B → (A ∨ B);
13) (B → A) → ((B → A) → B);
14) ((A → B) → A) → A – закон Пирса.
Пусть x1,x2,…,xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x1,x2,…,xn) принадлежат множеству M=(M1,M2,…Mn), которое будем называть предметной областью (т.е. xi∈Mi, где Мi называются областью определения переменной хi).
Определение 1 Предикатом местности n (n-местным предикатом), определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л.
Поскольку предикаты — это функции со значениями во множестве высказываний, где введены логические операции, то эти операции естественно определяются и для предикатов.
Определение 2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое ∀xP(x) (читается «для любого х Р(х)»}, которое истинно тогда и только тогда, когда Р(х) — тождественно истинный предикат. О высказывании ∀xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.
Определение 3. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое ∃xP(x) (читается «существует х Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании ∃xP(x) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х. Если множество определения переменной x конечно M={a1,a2,…,an}, то ∀xP(x)=P(a1)&P(a2)&…&P(an), ∃xP(x)=P(a1)∨P(a2)∨…∨P(an).
Обычно, связки и кванторы упорядочиваются по приоритету следующим образом: ¬, (∀,∃),
&, ∨, →, ∼.
Имеют место следующие равносильности:
1. Законы де Моргана: ∀xP (x) = ∃x P(x) , ∃xP (x ) = ∀ x P (x ) .
2. Коммутативность: ∀x∀yP(x, y) = ∀y∀xP(x, y) , ∃x∃yP(x, y) =∃y∃xP(x,y) .
3. Дистрибутивность:
∀x(P(x) &Q(x)) =∀xP(x) &∀xQ(x) , ∃x(P(x)∨Q(x)) =∃xP(x)∨∃xQ(x). 4. Для любого двухместного предиката ∃y∀xP(x,y) →∀x∃yP(x,y) =1.
Пример 9.1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2» — двуместный предикат, определенный на множестве пар натуральных чисел M=N×N. Очевидно, D(4,2) = И, D(3,5) =Л.
Пример 9.2. Q(x) = «x2 < -1, х∈R» — одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(-1) = Л, Q(5) = Л, и вообще предикат Q(x) — тождественно ложен, т. е. Q(x) = Л для всех х∈R.
Пример 9.3. В(x,у,z) =«х2+y2<z; х,у,z∈R.» — трехместный предикат, определенный на R3. В(1,1,-2)=Л, В(1,1,2)=И.
Пример 9.4. Определить таблицу истинности предиката∀xP(x, у) ⋅∨Q(x, у) , где предикаты определены таблицами ( где И-1, Л-0)
Решение. ∀xP(x, у) ⋅∨Q(x, у) =(∀xP(x, у))⋅∨Q(x, у) = ϕ(х, у) . Построим таблицу истинности предиката∀xP(x, у)⋅ = ϕ1(у):ϕ1(А) =∀xP(x,А)=0, ϕ1(В) =∀xP(x,В)=1,ϕ1(С) =∀xP(x,С)=0 т.е.
Найдем значения ϕ(х,у) :
ϕ(0,А) = ϕ1(А) ∨ Q(0,А) = 0 ∨1 = 1; ϕ(1,А) = ϕ1(А) ∨ Q(1,А) = 0 ∨ 0 = 0;
ϕ(2,А) = ϕ1(А) ∨ Q(2,А) = 0 ∨1 = 1,ϕ(0,В) = ϕ1(В) ∨ Q(0,В) = 1∨ 0 = 1; и т.д. для каждого
значения из исходной таблицы истинности. Получим
9.1. Пусть даны предикаты: Р(х): «х –четное число» и Q(x): «х кратно 3», определенные на множестве N={1,2,3,4,5,6,7,8,9,10,11,12,13}. Найти области истинности предикатов:
а) Р(х)&Q(x); б) P(x)∨Q(x); в) Р(х) ; г) P(x)→Q(x).
9.2. Даны предикаты Р(х)={х2+х+1>0} и Q(х)={х2-4х+3=0}, определенные на множестве R. Требуется установить, какие из следующих высказываний истинны и какие ложны: а) ∀хР(х); б) ∃хР(х); в) ∀хQ(x); г) ∃хQ(x).
9.3. Какие из следующих выражений являются формулами логики предикатов. В каждой формуле выделите свободные и связанные переменные:
а) (p→q)&(r ∨ p ); б) Р(х)&∀xQ(x); в) ∀х(Р(х)→Q(x))↔(∃xP(x) →∀xR(x,y));
г) (P(x)↔Q(x))∨ ∃y (∀yR(y)); д) ∃х ∀x(P(x,y)→P(y,z)).
9.4. Дана формула ∀x (P(x)&Q(x) →R(x)), где предикаты Р(x), Q(x) и R(x) определены на множестве N. Найти значение формулы, если:
а) Р(x): «Число х делится на 3», Q(x): «Число х делится на 4», R(x): «Число х делится на 2».
б) Р(х): «Число х делится на 3», Q(x): «Число х делится на 4», R(x): «Число х делится на 5».
9.5. Вычислить значения формулы ∀х ∃у Р(х,у) → ∃х∀у Р(х, у), где предикат Р(х,у)={х < у | x∈N, y∈ N}.
9.6. Пользуясь основными равносильностями логики предикатов, найдите отрицания следующих формул:
а) ∀х(Р(х)&Q(x)); б) ∃x(P(x)∨Q(x)), в)∀x ∃y(R(x,y)→L(x,y)).
9.7. Найти область истинности предиката
1. Р(х,у)=∃хР(х, у) ∨ Q(x, )y , где Р(х,у): « х+у – четно», Q(x,y): «х ≤ у»,х∈{1,2,6}, у∈{3,9}.
2. а) Р(х)⋅Q( )x ; б)∃xP(x) ∨ Q( )x ; в) ∀xP(x) ⋅Q( )x ;
если Р(х): «х четное натуральное число < 10», а Q(x): «x натуральное число кратное 3 и меньше 10».
4. а) ∃хР(х, у) ↔ Q(x, y) ; б) ∃xQ(x, y)→ ∀xP(x, y).
7. а)∃уP(x, y) ∧∀хQ(x, y) ; б) ∃xP(x, y → ∀xQ(x, y)).
8. а) ∃yP(x,y) → ∀xQ(x,y)⋅; б) ∀x∃yP(x, y).
9. а) ∃yP(x,y) → ∀xQ(x,y) ⋅ P(x,y);б) ∃y∀xQ(x,y).
Формальная теория (или исчисление) Ψ есть четверка (А,F,B,R):
1. множество A символов, образующих алфавит; конечные последовательности символов из А образуют множество S слов (выражений);
2. множество F слов в алфавите A, F⊂S, которые называются формулами;
3. подмножество B формул, B⊂F, которые называются аксиомами;
4. множество отношений R на множестве формул, которые называются правилами вывода.
Множества A и F в совокупности определяют язык, или сигнатуру, формальной теории Ψ.
Формула G называется теоремой исчисления Ψ (выводимой в Ψ или доказуемой в Ψ), если существует вывод F1,F2,…,Fn,G который называется доказательством теоремы G. Записывается это следующим образом: F1,F2,…,Fn├ G.
Исчисление Ψ называется непротиворечивым, если в нем не являются выводимыми одновременно формулы F и ¬F (отрицание F).
Исчисление Ψ называется полным (или адекватным), если каждому истинному высказыванию М соответствует теорема теории Ψ.
Формальная теория Ψ называется разрешимой, если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой теории Ψ или нет.
Одним из важных примеров аксиоматической теории может служить исчисление высказываний ИВ (один из способов формализации логики высказываний), которую можно определить следующим образом:
Алфавит ИВ состоит из
1. букв (пропозициональных переменных) А, В, Q, R, Р и других,
2. логических символов (связок) ¬, &, ∨, →,
3. вспомогательных символов-скобок: ( , ).
Множество формул ИВ определяется индуктивно:
1. все пропозициональные переменные являются формулами ИВ;
2. если A, B —.формулы ИВ, то ¬A, A∧B, A∨B, A→B — формулы ИВ;
3. выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "1" и "2".
Таким образом, любая формула ИВ строится из пропозициональных переменных с помощью связок ¬, ∧, ∨, →.
Аксиомами ИВ являются следующие формулы (система Клини):
для любых формул A,B,C
1. A→(B→A);
2. (A→B)→((A→(B→C))→(A→C));
3. (A∧B)→A;
4. (A∧B)→B;
5. (A→B)→((A→C)→(A→(B∧C)));
6. A→(A∨B);
7. A→(B∨A);
8. (A→C)→((B→C)→((A∨B)→C));
9. (A→B)→((A→¬B)→¬A);
10. ¬¬A→A.
Правилом вывода в ИВ является правило заключения {modus ponens): если A и A→B — выводимые формулы, то B — также выводимая формула.
A , A → B
Символически это записывается так: B .
Говорят, что формула G выводима из формул F1,F2,…,Fn (обозначается F1,F2,…,Fn├G), если существует последовательность формул F1,F2,…,Fk,G, в которой любая формула является либо аксиомой, либо принадлежит списку формул F1,F2,…,Fn (называемых гипотезами), либо получается из предыдущих формул по правилу вывода. Выводимость формулы G из ∅ (обозначается ├G) равносильно тому, что G — теорема ИВ.
Формула A называется тавтологией (тождественно-истинной формулой), если при любых значения переменных списка (x1, x2, ..., xk) она принимает значение И. Формула A называется выполнимой (условно-истинной формулой), если при некоторой значениях переменных списка (x1, x2, ..., xk) она принимает значение И. Формула A называется тождественноложной формулой, если при любых значениях переменных списка (x1, x2, ..., xk) она принимает значение Л. Формула A называется опровержимой (условно-ложной формулой), если при некоторых значениях переменных списка (x1, x2, ..., xk) она принимает значение Л. Отметим, что формальная аксиоматическая теория является полной, если в ней доказуема любая тавтология.
Теорема 10.1. Пусть Г — набор некоторых формул Г={F1,F2,…,Fn} ИВ.
1. Если A,B — формулы ИВ и Г├A, то Г,B├A. (можно увеличивать число гипотез).
2. F1,F2,…,Fn├A ⇔ F1∧F2∧…∧Fn├A (сведение множества гипотез к одной гипотезе).
Теорема 10.2. (теорема о дедукции) Если Г,B├A, то Г├B→A, где Г — набор некоторых формул Г={F1,F2,…,Fn}.
Следствие. F1,F2,…,Fn├A, ⇔ F1→(F2→…→(Fn-1→(Fn→A))…)
Теорема 10.3. (о полноте). Формула A доказуема тогда и только тогда, когда A тождественно истинна: ├A равносильно,что A−тавтология.
Таким образом, для того чтобы установить, доказуема ли формула, достаточно составить ее таблицу истинности. Как известно, существуют алгоритмы построения таблицы истинности, и, значит, ИВ разрешимо.
Приведем список соответствия связок ИВ наиболее часто встречающимся выражениям, и который призван помочь в построении формул ИВ.
|
A~B |
A если и только если B Если A, то B, и обратно A, если B, и B, если A Для A необходимо и достаточно B A равносильно B A тогда и только тогда, когда B |
|
A→B |
Если A, то B B, если A A, только если B A влечет B Коль скоро A, то B В случае A имеет место B Для B достаточно A Для A необходимо B |
|
A∧B |
A и B Не только A, но и B B, хотя и A |
|
|
B, несмотря на A Как A, так и B A вместе с B A, в то время как B |
|
A∨B |
A или B A или B, или оба A, если не B |
|
¬A |
A не имеет места A не верно "не" перед глаголом |
|
A⊕B (A∨B)∧¬(A∧B) (A∧¬B)∨(¬A∧B) ¬(A→B)∨¬(B→A) (¬B→¬A)∨(¬A→¬B)
|
A либо B, но не оба Или A, или B Либо A, либо B (иногда) A, если не B (иногда) A, кроме случая когда B (иногда) A или B (иногда) |
|
¬(A∨B) |
Ни A, ни B |
Пример 10.1. Используя теорему о дедукции и теорему о полноте проверить выводимость
формулы ИВ: А→В, В→А ├ AB ∨ BA.
Решение: Используя теорему о дедукции последовательно, заключаем, что А→В, В→А ├
AB ∨ BA ⇔
А→В ├ (В→А)→( AB ∨ BA) ⇔ ├ (А→В)→((В→А)→ →( AB ∨ BA)).
По теореме о полноте заключаем, что формула ϕ=(А→В) ((В→А)→( AB ∨ BA)) доказуема тогда и только тогда, когда ϕ является тавтологией. Построим таблицу истинности для формулы ϕ.
AB ∨ BA не выводится из формулы А→В и В→А.
Пример 10.2. Покажем, что формула A→A выводима в ИВ. Для этого построим вывод данной формулы:
1) в аксиоме 2 заменим B на A→A, C — на A. Получаем аксиому
(A→(A→A))→((A→((A→A)→A))→(A→A));
2) в аксиоме 1 заменим B на A. Получаем A→(A→A);
3) из 1 и 2 по modus ponens заключаем (A→((A→A)→A))→(A→A);
4) в аксиоме 1 заменяем B на A→A. Получаем A→((A→A)→A); 5) из пп. 3 и 4 по правилу вывода справедливо├ A→A.
Пример 10.3. На предприятии есть три цеха: A, B, C, договорившиеся о порядке утверждения проектов, а именно:
1. Если цех B не участвует в утверждении проекта, то в этом утверждении не участвует и цех A.
2. Если цех B принимает участие в утверждении проекта, то в нем принимают участие цеха A и C.
Спрашивается, обязан ли при этих условиях цех C принимать участие в утверждении проекта, когда в нем принимает участие цех A?
Решение. Логические переменные: «А участвует в утверждении проекта» обозначим через А, «В участвует в утверждении проекта» – В, «С участвует в утверждении проекта» – С.
Посылки: P1 − (B → A), P2 − (B → A & C) . Утверждение D−(A →C). Надо выяснить, верны ли рассуждения, т.е. выяснить будет ли тавтологией формула:
(B →
A) &(B → AC)
→ (A → C). Имеем
(B → A) & (B → AC) →
(A → C) = (B ∨ A)(B ∨ AC) ∨ (A ∨ C) =
= BA ∨ B(A ∨ C) ∨ A ∨ C = AB ∨ AB∨ BC ∨ A ∨ C = B ∨ A ∨ B∨ C =1, следовательно, рассуждения верны.
В задачах 10.1.-10.7 переведите каждое из следующих рассуждений в логическую символику и проанализируйте результат на правильность:
10.1. Я бы заплатил за работу по ремонту телевизора, только если бы он стал работать. Он же не работает. Поэтому я платить не буду.
10.2. Если бы он ей не сказал, она ни за что не узнала бы. А не спроси она его, он бы и не сказал ей. Но она узнала. Значит, она его спросила.
10.3. Он сказал, что придет, если не будет дождя. Но идет дождь. Значит, он не придет.
10.4. Если он принадлежит к нашей компании, то он храбр и на него можно положиться. Он не принадлежит к нашей компании. Значит, он не храбр или же на него нельзя положиться.
10.5. Если подозреваемый совершил эту кражу, то либо она была тщательно подготовлена, либо он имел соучастника. Если бы кража была подготовлена тщательно, то, если бы был соучастник, украдено было бы гораздо больше. Значит, подозреваемый невиновен.
10.6. Намеченная атака удастся, только если захватить противника врасплох или же если позиции его плохо защищены. Захватить его врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Значит, атака не удастся.
10.7. Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжет. Следовательно, Смит был убийцей.
10.8. (Задача Кислера) Браун, Джонс и Смит обвиняются в подделке сведений о подлежащих налоговому обложению доходах. Они дают под присягой такие показания:
Браун: Джонс виновен, а Смит невиновен.
Джонс: Если Браун виновен, то виновен и Смит.
Смит: Я невиновен, но хотя бы один из них двоих виновен.
Обозначим через Б, Д и С высказывания: «Браун невиновен», «Джонс невиновен», «Смит невиновен». Выразите показания каждого из обвиняемых формулой. Постройте для этих формул таблицы истинности. Затем ответьте на следующие вопросы:
1) Совместимы ли показания всех троих заподозренных (т.е. могут ли они быть верны одновременно)?
2) Показания одного из обвиняемых следуют из показаний другого; о чьих показаниях идет речь?
3) Если все трое невиновны, то кто совершил лжесвидетельство?
4) Предполагая, что показания всех обвиняемых верны, укажите, кто невиновен, а кто виновен?
5) Если невиновный говорит истину, а виновный лжет, то кто невиновен, а кто виновен?
10.9. Существуют ли в ИВ следующие выводы:
1) ├A∨B→A∨C, 2) ├((A→B) →B)→A, 3) ├((A→B)→B)→B,
4) ├ ¬(A∨¬A)→(A∨¬A), 5) A├ ¬(A→ ¬A), 6) A→B├ B→A, 7) ├A∧B→(A→C), 8) ├((A→B) →A)∨A, 9) ├(A∧B∨A)→B.
10.10. Построить в исчислении высказываний следующие выводы:
|
1) A├A; |
2) ├A→A; 3) ├(A∧A)→A; |
|
4) A→B, B→C├A→C; |
5) A→B, ¬B├ ¬A; 6) A→B├ ¬B→ ¬A; |
|
7) ├ A→ ¬¬A; |
8) ├ (¬¬A→A)∧(A→ ¬¬A). |
10.11. Построить в исчислении высказываний следующие выводы:
|
1) A→(B→C)├ B→(A→C), |
2) A→(B→C)├ (A∧B)→C, |
|
3) (A∧B)→C├A→(B→C), |
4) A→(B∨C)├ (A∧B)→C, |
|
5) A→B├ (C→A)→(C→B), |
6) A→B├ (C∧A)→(C∧B), |
|
7) A→B├ (A∧C)→(B∧C), |
8) A→B├ (A∨C)→(B∨C), |
|
9) A→B├ (C∨A)→(C∨B), |
10) ¬A├ A→B, |
|
11) A├ ¬A→B, |
12) A→B├ ¬B→ ¬A, |
|
13) A→ ¬B├ B→ ¬A, |
14) ¬A→B├ ¬B→A, |
|
15) ¬A→ ¬B├ B→A, |
16) ├ A∨(A∧B)→A, |
|
17) ├A→A∧(A∨B), |
18) ├A∨¬A, |
|
19) ├ ¬(A∧¬A), |
20) ├ (A∧B)∧C→A∧(B∧C). |
Тезис Чёрча. Понятие алгоритма, или вычислимости некоторым механическим устройством, совпадает с понятием вычислимости на машинах Тьюринга (а значит, с понятием рекурсивной функции). Другими словами, алгоритм − это процесс, который может быть представлен функциональной схемой и реализован некоторой машиной Тьюринга.
Машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки (СЗУ).
Лента разбита на ячейки. Во всякой ячейке содержится в точности один символ из внешнего алфавита A={a0,a1,…,an}. Некоторый символ (будем обозначать его ∧) алфавита A называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны.
Управляющее устройство в каждый момент времени находится в некотором состоянии qj, принадлежащем множеству Q={q0, q1,..., qm} (m=l). Множество Q называется внутренним алфавитом. Одно из таких состояний (обычно q0) называется заключительным, а некоторое другое (обычно q1) -начальным.
Считывающая головка перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое обозреваемой ячейки и записывать в нее вместо обозреваемого символа некоторый новый символ из внешнего алфавита A (возможно тот же самый). В процессе работы управляющее устройство в зависимости от состояния, в котором оно находится и символа, обозреваемого головкой, изменяет свое внутреннее состояние q. Затем выдает головке приказ напечатать в обозреваемой ячейке определенный символ из внешнего алфавита A, а потом приказывает головке либо остаться на месте, либо сдвинуться на одну ячейку вправо, либо сдвинуться на одну ячейку влево. Попав в заключительное состояние, машина прекращает работу.
Конфигурацией на ленте (или машинным словом) называется совокупность, образованная: 1) последовательностью a i (1) , a i ( 2 ) ,..., a i ( s ) символов из внешнего алфавита А, записанных в ячейках ленты, где ai(1).- символ записанный в первой ячейке слева (отличный от пустого) и т.д., 2) состоянием внутренней памяти qr; 3) номером k воспринимаемой ячейки. Конфигурацию машины будем записывать так:
a i(r )
a i(1) , a i(2) ,..., a i(r
−1) 
a i(r +1) , a i(r +
2) ,..., a i( s) q r
здесь r-воспринимаемая ячейка, выделяется в виде дроби. a i (1) , a i ( 2 ) ,..., a i ( s )
Если машина, находясь во внутреннем состоянии qi , воспринимает ячейку с символом au , записывает к следующему моменту времени в эту ячейку символ ar , переходит во внутреннее состояние qs и сдвигается по ленте, то говорят, что машина выполняет команду qiau→qsarS , где символ S может принять одно из значений: -1 – сдвиг головки влево; +1 - сдвиг головки вправо; 0 – головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении строки ai и столбца qi будет стоять qsarS ( см. таб.6.2.1). Если в программе машины для пары (qi,au) пятерка отсутствует, то в таблице на пересечении строки au, и столбца qi ставится прочерк.
Итак, машина Тьюринга есть, по определению, набор М=(А,Q,П), где А ― внешний алфавит, Q ― алфавит внутренних состояний, П ― программа.
Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.
Пример 11.1. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (записанные при помощи одного символа |, например 5=|||||.). Решение. Рассмотрим алфавит А = {|, +, ∧}. Машина определяется следующей программой:
Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+|||, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.
Пример 6.2.2. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.
Решение. Искомую машину построим в алфавите A={|, α, ∧}. Программа такой машины может выглядеть так:
Применим полученную машину к слову ||.
Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q1 беспечивает замену | на α, состояние q2 обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена α на |.
В этом разделе содержатся задачи двух типов: 1. по заданной машине Тьюринга найти результат ее применения к заданному слову u, т.е. T(u); 2. построение машины, решающей данный класс задач.
Естественные трудности возникают при решении задач второго типа. Здесь рекомендуется до составления программы машины, т.е. до заполнения таблицы, задающей программу, тщательно продумать алгоритм, который должен быть реализован программой. В конце решения, т.е. когда программа составлена, не забудьте применить ее к тестовому примеру.
В задачах 10.1 и 10.2 по заданной машине
Т с внешним алфавитом A ={
},∧ и слову
u найти Т(u).
В задачах 10.3 и 10.4 выяснить, применима ли машина Т с внешним алфавитом {⎜;∧} к слову u, в случае применимости найти результат:
10.5. Построить машину К2 над алфавитом {⎜}.
10.6. Построить машину К1 над алфавитом {α;β}.
10.7 Какую функцию натурального аргумента вычисляет машина, заданная программой П.
Постарайтесь упростить эту машину.
10.8. Постройте машину, распознающую четность натурального числа.
10.9. Постройте машину Rm, вычисляющую остаток от деления натурального числа на m.
10.10. Постройте машины Тьюринга, вычисляющие следующие функции, заданные на
N×N: а) x+y; б) x+2y; в) x y⋅ , г)x2+3y.
10.11. Постройте машины Тьюринга, вычисляющие следующие функции, определенные на N:
а) 3x; б) x2; в) f( )x = ⎧⎨x +1, еслих = 2n
⎩2x, еслих = 2n +1
10.12. Постройте машину над алфавитом {⎜}, применимую к любому слову четной длины и не применимую к словам нечетной длины.
В задачах 10.13–10.17 постройте в алфавите {0;1} машину Т, работающую по правилу:
def
10.13. T(1n)= 1n011, n∈N, an = aa " a.
n
10.14. T(0n1n)= ( )01 n,n ∈ N .
10.15. T(1n)= 1n012n013n,n ∈ N .
10.16. T(1n01m)= 1m01n,n,m ∈ N .
⎧12n ,если n > m;
⎪
10.17. T(1n0m )= ⎪⎨( )01 n , если n = m;
⎪ m
⎪⎩0 ,если n < m.
10.18. Какую функцию натурального аргумента вычисляет машина Т?
10.19. Какие одноместные функции натурального аргумента в алфавите {⎜;∧} могут вычислять машины, программы которых содержат только команды q0 и q1?
10.20. По словесному описанию машин Т3, Т4 программы. Внешний алфавит {0;1;∧}.
Т3- начиная с последней единицы массива из единиц, «сдвигает » его на одну ячейку а лево и останавливается на первой единице;
Т4 – при заданном l ≥1 СЗУ машины, начав с произвольной ячейки, заполненной единицей, движется вправо, не меняя содержимого ячеек, до тех пор пока не пройдет массив из l+1 ноля; СЗУ останавливается для следующей ячейке, поместив туда единицу.
1. Построить таблицу истинности функции.
f = (x ⋅ y ⊕ z) → x | y.
2. Является ли функция f самодвойственной?
f = x → x ⋅ y.
3. Привести функцию f к КНФ, ДНФ.
f = x ∨ y ↔ z ∨ y.
4. Построить СДНФ и СКНФ.
а) f
= z∨ y⋅z∨x⋅ y⋅z. б)
f = ( 1011 0110 ).
5. Построить полином Жегалкина, методом неопределенных коэффициентов:
а) f = (x
| y)∨ x ⋅ y ; б)
(1101 0011).
6. Используя карты Карно построить минимальную ДНФ, КНФ если:
а) (0100 1100 1111 0100).
7. Найти СДНФ и СКНФ по карте Карно, изображенной в задаче 6.в).
8. Построить минимальную ДНФ, КНФ методом Квайна если: f(1,0,0,1)=f(1,0,0, 0,)=f(1,0,1,0)=f(1,1,0, 1)=f(1,1,0,0)=1
9. Найти область истинности предиката
а) ∀xP(x, y) → ∃yQ(x, y) ∨ P(x, y); б) ∀x∃yP(x, y)
10. Построить в исчислении высказываний следующие выводы:
a) ├ ¬A∧¬B→ ¬(A∨B), б) ¬(A∧B)├ ¬A∨¬B.
Сравнить приведенные формулы с законами де Моргана из алгебры логики.
1. ЕрусалимскийЯ.М. Дискретная математика/ М., «Вузовская книга», 2001г.,279С.
2. Дискретная математика. Функции алгебры логики. /Учебное пособие. Составители:
Н.А. Ахметова, З.М. Усманова, Уфимский государственный авиационный технический университет, 2001г., 106С.
3. Новиков Ф.А. Дискретная математика для программистов./ Санкт-Петербург: Питер, 2001г., 304С.
4. Судоплатов С.В., Овчинникова Е.В. Элементы Дискретной математики./ М., ИНФРА-М, Новосибирск, Изд-во НГТУ, 2002г., 208С.
5. Шапорев С.Д. Математическая логика. Курс лекций и практических занятий/ СанктПетербург: БХВ-Петербург, 2005г., 410С.
6. Гиндикин С.Г. Алгебра логики в задачах. М.:Наука, 1972.
7. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. / М. Наука,1992.
8. Математическая логика /Методические указания к практическим занятиям и выполнению РГР по курсу «Дискретная математика», составители: М.Э.Рояк, С.Х.Рояк, Новосибирский государственный технический университет, 1998г.
9. Лихтарников Л.М. Первое знакомство с математической логикой./ Санкт-Петербург: Лань, 1997г., 110С.
10. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М: Наука, 1975г.
11. Нефедов В.Н., Осипова В.А.. Курс дискретной математики./ М., Изд-во МАИ, 1992г., 264С.
12. Сборник задач по математической логике и теории множеств. Саратов: Изд. СГУ, 1969г.
Рабочие листы
к вашим урокам
Скачать
Рабочие листы
к вашим урокам
Скачать
6 655 094 материала в базе
Настоящий материал опубликован пользователем Каверина Ирина Александровна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
36 ч. — 144 ч.
Мини-курс
6 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.