Функции алгебры логики в примерах и задачах. Киселева Л.Г

2.8. Задачи и упражнения по функциям алгебры логики

Функции алгебры логики в примерах и задачах. Киселева Л.Г

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

– коммутативность связки *, где символ * является общим обозначением для связок &, Ú, Å, ~, |, ¯.

– ассоциативность связки *, где *– общее обозначение для связок &,Ú,Å,~.

Дистрибутивность

А) – дистрибутивность конъюнкции относительно дизъюнкции;

Б) – дистрибутивность дизъюнкции относительно конъюнкции;

В) – дистрибутивность конъюнкции относительно сложения по mod 2.

4. а) ; б) суть правила де Моргана;

5. а) ; б) суть правила поглощения;

6. а) ; б) ;

7. а) ; б) ;

В) ; г) ; д) ;

8. а) ;

Б) ; в) ;

9. а) ; б) .

1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :

, ;

,

, ;

, ;

, ;

, ;

, ;

, ;

, ;

, .

Ответы: 2), 6), 9), 10) – эквивалентны; 3), 7) – не эквивалентны.

2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

;

;

;

;

;

;

;

;

;

;

.

3. Используя приведенные выше основные эквивалентности и соотношения докажите эквивалентность формул V и U:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы:

4) ;

9)

4. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция G двойственной к функции F:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , ;

11) , ;

12) , .

Ответы: 4) , . Значит, G не двойственна к F. 6) – не является; 8),9),11) – является.

5. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции F, и убедитесь в том, что полученная формула эквивалентна формуле V:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы:

1)

2) ; 5) ; 10) .

6. Указать все фиктивные переменные у функции F:

1)

2)

3)

4)

5)

6)

Ответы:1)две фиктивные переменные; 3)одна фиктивная переменная; 5)фиктивные переменные X1 и X3.

7. Показать, что X1 – фиктивная переменная у функции F (реализовав для этой цели функцию F формулой, не содержащей явно переменную X1):

1) ;

2) ;

3) ;

4) 5) 6) 7)

8) 9) 10)

Ответы: 4),8),10) 9)

8. Выяснить, можно ли из функции F , отождествляя и переименовывая в ней переменные, получить функцию G:

1) ,

2) ,

3) ,

4) ,

5) ,

6) ,

7) , ;

8) , ;

9) , ;

10) , .

Ответы: 1),2),5),7),8),9),10)можно. 3),4),6)нельзя.

9. Представить в СДНФ следующие функции:

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2) ; 4) , 7)

10. Представить в СКНФ следующие функции:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1) ; 2) ; 6) ; 8)

11. С помощью эквивалентных преобразований построить ДНФ функции

:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

4)

10)

12. Используя эквивалентные преобразования, построить КНФ функции

:

1)

2) ;

3)

4)

5)

6)

7)

Ответы:

1)

3)

6)

13. Применяя преобразования вида и построить из заданной ДНФ функции ее совершенную ДНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

2)

5)

14. С помощью преобразований вида и построить из данной КНФ функции ее совершенную КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

1)

5)

15. Используя дистрибутивный закон и эквивалентности и перейти от заданной КНФ функции к ДНФ:

1)

2)

3)

4)

5)

6)

7)

Ответы:

3)

6)

16. Используя дистрибутивный закон и эквивалентности и перейти от заданной ДНФ функции к ее КНФ:

2)

3)

4)

5)

6)

7)

8)

Ответы:

2)

5)

17. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

1) 3) 6)

10)

18. Методом треугольника Паскаля построить полином Жегалкина для этой функции, если:

1) 2)

3) 4)

5) 6)

7) 8)

9) 10)

Ответы:

1) 4) 7)

19. Представив функцию формулой над множеством связок {&, }, преобразуйте полученную формулу в полином Жегалкина функции (используя эквивалентности ):

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

1)

3)

9)

20. Построить множество всех функций, зависящих от переменных X1,X2 и принадлежащих замыканию множества А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1) 2) 3)

4) 5) 6)

21. Покажите, что , выразив формулой над множеством А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1) 2) 3) 4) 5) 6) 7)

22. Выписать все попарно неконгруэнтные функции , принадлежащие замыканию множества А:

1) 2) 3) 4)

5) 6) 7) 8) 9) 10)

Ответы: 1) 2) 3) 4) 5)

23. Из полной для класса [A] системы выделить базис:

1) 2) 3) 4)

5) 6)

7) 8) 9) 10)

Ответы: 1) 2) 3) 4) 5)

24. Сведением к заведомо полным системам в P2 показать, что множество А является полной системой в P2:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1)система является полной в P2, поскольку всякая может быть представлена в виде ДНФ или КНФ. С другой стороны,

2) имеем Система полна, поскольку

3) имеем ;

4) имеем ;

5) имеем ;

25. Выяснить, является ли функция F самодвойственной:

1)

3)

5)

7)

2)

4)

6)

8)

9)

11)

13)

15)

10)

12) 14)

Ответы: 1),3),4),8),10) – является; 2),5),6),7),9) – не является.

26. Выяснить, является ли самодвойственной функция F, заданная векторно:

1)

3)

5)

7)

9)

11)

13)

15)

2)

4)

6)

8)

10)

12)

14)

Ответы: 1),3),5),6),7),8) – является; 2),4),9),10) – не является.

27. Выяснить, является ли множество А самодвойственным:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1),3),5-7),10) – является; 2),4),8),9) – не является.

28. Представив функцию F полиномом, выяснить, является ли она линейной:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 2),3),5),6),8),9)–является. 1),4),7),10)–не является.

29. Выяснить, является ли линейной функция F, заданная векторно:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1),3),4),5),7),8),9),10) – является; 2),6) – не является.

30. Доказать, что система А полна в L. Выяснить, является ли система A базисом в L:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1)с помощью суперпозиции из функции можно получить любую функцию вида , путем подстановки 1-любую функцию вида Система А является базисом;

2),3),4),5),7),8),9) – является; 6),10) – не является.

31. Выяснить, принадлежит ли функция F множеству T1\T0:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1),3),4),6),8),9) – является; 2),5),7),10) – не является.

32. Подсчитать число функций, зависящих от переменных X1,…,Xn и принадлежащих множеству А:

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

18)

19)

20)

21)

22)

23)

24)

25)

26)

27)

28)

29)

30)

31)

32)

33)

34)

35)

36)

37)

38)

39)

40)

41)

42)

43)

44)

45)

Ответы: 1) ; 2) ; 3)22N; 4) ; 5) 6)2N; 7) ; 8) ; 9) ; 10) ; 15) 0.

33. Доказать, что:

Указание: если то если то

34. Выяснить, является ли множество А базисом в классе К:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1)да. Имеем ;

2) А не является базисом в T1,так как ;

А не является базисом в T1,так как ;

А не является базисом в T1,так как ;

А не является базисом в T1,так как ;

А – базис в .

35. По вектору значений выяснить, является ли функция F монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 2),3),5),8) – является; 1),4),6),7) – не является.

36. Проверить, является ли функция F монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1),2),4),6),7) – является; 3),5),8) – не является.

37. Выяснить, полна ли система функций:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2),4),6) – полна; 1)нет, 3)нет, 5)нет,

38. Выяснить, полна ли система А функций, заданых векторами своих значений:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 3),5) – полна; 1)нет, 2)нет, 4)нет, 6)нет,

39. Выяснить, полна ли система А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1),4),6) – полна; 2)нет, 3)нет, 5)нет,

40. Проверить, является ли система функций А базисом в Р2:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:1) нет, так как подсистема полна; 2) является; 3) не является, 4)нет, можно удалить

41. Из полной в Р2 системы А выделить всевозможные базисы:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1) где

2)

42. Используя теоретико – множественные операции, выразить через известные замкнутые классы T0, T1, L, S, M и P2 замыкания множества А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

Ответы: 1)P2; 2) 3) 4) 5) 6)

43. Выяснить, можно ли расширить до базиса в Р2 множество А:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1) можно, – базис; 2) нельзя, функция x входит во все предполные классы; 3) можно, – базис; 4) нет, функции и принадлежат одним и тем же предполным классам.

44. Выяснить, полна ли система функций

1)

2)

3)

4)

Ответы: 1)вообще говоря, нет. Рассмотреть

2)да, имеем

3) вообще говоря, нет. Рассмотреть

4) вообще говоря, нет. Рассмотреть

Источник: http://matica.org.ua/metodichki-i-knigi-po-matematike/metodichka-po-diskretnoi-matematike-s-primerami-reshenii/2-8-zadachi-i-uprazhneniia-po-funktciiam-algebry-logiki

Логические задачи в алгебре логики с примерами, решениями и ответами

Функции алгебры логики в примерах и задачах. Киселева Л.Г

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

  • средствами алгебры логики;
  • табличный;
  • с помощью рассуждений.

Познакомимся с ними поочередно.

 Обычно используется следующая схема решения:

1.      изучается условие задачи;

2.      вводится система обозначений для логических высказываний;

3.      конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4.      определяются значения истинности этой логической формулы;

5.      из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1. Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

Джон: ¬Ш/\Х

Ник: Ш/\¬А

Питер: ¬Х

  Высказывание Ш /\ ¬ А/\ ¬Х  истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

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

 
 Пример 2. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

  1. Смит самый высокий;
  2. играющий на скрипке меньше ростом играющего на флейте;
  3. играющие на скрипке и флейте и Браун любят пиццу;
  4. когда между альтистом и трубачом возникает ссора, Смит мирит их;
  5. Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

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

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов «альт» и «кларнет» заполним нулями:

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки «Вессон» можно заполнить нулями:

Из таблицы видно, что играть на флейте и на гобое может только Смит.

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

Этим способом обычно решают несложные логические задачи.

 Пример 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский.

На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский».

Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

  1. Вадим изучает китайский;
  2. Сергей не изучает китайский;
  3. Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

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

Остается считать верным третье утверждение, а первое и второе — ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.

Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.

Пример 4. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: «Чей именно проект был принят?», министры дали такие ответы:

Россия — «Проект не наш, проект не США»;
США — «Проект не России, проект Китая»;
Китай — «Проект не наш, проект России».

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия — «Проект не наш»   (1),   «Проект не США»   (2);
США —   «Проект не России»   (3),   «Проект Китая»   (4);
Китай —   «Проект не наш»   (5),   «Проект России»   (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный — министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

Источник: https://mir-logiki.ru/log_zadachi/

1 ББК 22.174 © Нижегородский государственный Университет им. Н.И. Лобачевского, 2008 2 Глава 1. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 1.1. Основные понятия и определения Пусть E 0,1. Набор

Функции алгебры логики в примерах и задачах. Киселева Л.Г

Книги по всем темамPages:     || 2 | 3 | 4 | 5 | ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Нижегородский государственный университет им. Н.И.Лобачевского Л.Г. Киселева, Т.Г.

Смирнова Функции алгебры логики в примерах и задачах Учебно-методическое пособие Рекомендовано методической комиссией факультета вычислительной математики и кибернетики для студентов ННГУ, обучающихся по направлениям подготовки 010500 «Прикладная математика и информатика», 010400 «Информационные технологии» Нижний Новгород 2008 УДК 519.95 ББК 22.174 К – 44 К-44 Киселева Л.Г.

, Смирнова Т.Г. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ В ПРИМЕРАХ И ЗАДАЧАХ: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2008. – 57 с.

Рецензент: д. физ.-мат. наук, проф., зав. каф. ИИТ НГПУ М.А. Иорданский В учебно-методическом пособии изучаются основные понятия и различные представления функций алгебры логики.

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

Учебно-методическое пособие предназначено для студентов факультета ВМК, изучающих общий курс “Дискретная математика”.

УДК 519.95 ББК 22.174 © Нижегородский государственный Университет им. Н.И. Лобачевского, 2008 2 Глава 1. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 1.1. Основные понятия и определения Пусть E 0,1. Набор (1,2,…

,n ), где i E, называется булевым или n ~ двоичным набором и обозначается через. Число n называется длиной наn n n ~ ~ ~ бора, а число единиц в наборе – весом набора.

Каждому двоичному n n n n ~ ~ ~ набору можно сопоставить число ( ) 2ni – номер набора.

i i1 n n ~ ~ Набор является двоичным разложением своего номера ( ).

n E – множество всех двоичных наборов длины n.

n Функция f ( x1, x2,…, xn ), определенная на множестве E и принимающая значения из множества E, называется функцией алгебры логики или булевой n функцией от n переменных, т.е. f : E E. Набор символов переменных (x1, x2,…, xn ) будем обознаn ~ чать через x.

x1 x2 xn1 xn f ( x1, x2,…, xn1, xn ) … n ~ f (0, 0,…,0, 0) Булеву функцию f ( x ) 0 0 … 0 f (0, 0,…,0,1) при n 1 можно задать таб- 0 0 … 0 лицей (табл. 1.1), в которой f (0,0,…,1,0) 0 0 … 1 n ~ … … … … … … наборы (1,2,…,n ) f (1,1,…,1,1) 1 1 … 1 располагаются в порядке возрастания их номеров.

Имея в виду такое стан- Табл. 1.1. Табличное задание булевой функции дартное расположение на- n ~ боров, булеву функцию f ( x ) удобно задавать вектором ее значений:

n ~ f (~ n ) ( f0, f1,…, f2n ), где координата fi равна значению функции f ( x ) x на наборе, имеющем номер i (i 0,1,…, 2n 1).

Пусть P2 (n) – множество всех булевых функций от n переменных, т.е.

n n P2 n=f~ f : E E.

x Теорема 1.1.1. Мощность P2 n множества всех булевых функций от n n переменных равна 22.

Доказательство. Так как функцию алгебры логики от n переменных можно задать упорядоченным двоичным набором длины 2n, то число различных функций алгебры логики от n переменных равно числу всех двоичных наборов n длины 2n, т.е. 22. Теорема доказана.

С ростом числа переменных таблица, задающая булеву функцию, сильно усложняется, становится громоздкой. Число функций от n переменных быстро растет: P2 1 4, P2 2 16, P2 3 256, P2 4 65536.

Рассмотрим теперь элементарные функции алгебры логики.

Имеются четыре булевы функции от одной переменной (см. табл. 1.2). Эти функции носят соответственно следующие названия:

x 0 x x 0 – константа нуль.

0 0 0 1 x – тождественная функция.

1 0 1 0 x – отрицание x, читается как «не x ».

1 – константа единица. Табл.1.2. Функции одной переменной y x y x y x y x & y x y x y x x y 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 Табл. 1.3. Элементарные функции от двух переменных Приведенные в табл. 1.3 булевы функции от двух переменных носят следующие названия:

x & y – конъюнкция x и y, обозначается также x y или xy, читается «x и y».

x y – дизъюнкция x и y, читается «x или y».

x y – сложение по модулю 2 x и y, читается «x плюс y».

x y – импликация x и y, читается «из x следует y».

x y – эквивалентность x и y, часто обозначается как x ~ y, читается «x эквивалентно y».

x y — штрих Шеффера x и y, часто эта функция называется антиконъюнкцией, читается «не x или не y».

x y — стрелка Пирса x и y, часто эта функция называется антидизъюнкцией, читается «не x и не y».

Символы, &,,,,,,, участвующие в обозначениях элементарных функций, называются логическими связками.

Суперпозицией булевых функций f1,…, fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных.

Формулой в алгебре логики называется всякое (и только такое) выражение вида:

1) x – любая переменная из множества переменных X ;

2) ( F ), ( F1 F2 ), где F, F1, F2 – произвольные формулы алгебры логики, а &,,,,,, – логическая связка.

Обычно внешние скобки у формул не записываются. Обратим внимание, что связка отрицания сильнее, чем любая двухместная связка, а связка & – самая сильная из связок,,,,,. Эти соглашения позволяют упрощать запись формул и не писать ряд скобок. Например, формула (((x y) & z) ((x & z) ( y & z))) записывается как (x y)z (xz yz).

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

В отличие от табличного задания представление данной функции формулой не единственно.

Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными.

Рассмотрим далее некоторые эквивалентности, характеризующие свойства элементарных булевых функций.

Основные эквивалентности алгебры логики 1. Функция x y, где &,,,,,, обладает свойством коммутативности: x y y x.

2. Функция x y, где &,,,, обладает свойством ассоциативности: (x y) z x ( y z).

3. Дистрибутивные законы:

(x y) & z (x & z) (y & z) ;

(x & y) z (x z) & (y z) ;

(x y) & z (x & z) ( y & z).

4. Законы де Моргана:

а) x & y x y ; б) x y x & y.

5. Законы поглощения:

а) x (x & y) x ; б) x & (x y) x.

6.

а) x (x & y) x y ; б) x & (x y) x & y.

7.

a) x & x x & 0 x x 0; б) x x x 1 x x 1.

8. а) x & x x x x &1 x 0 x 0 x ;

б) x 1 x 0 x 0 x x x x x ;

9. а) x y (x & y) (x & y) (x y) & (x y);

б) x y x y ;

в) x y x y (x & y) (x & y) (x y) & (x y) ;

г) x y x & y x y ;

д) x y x y x & y.

В справедливости этих эквивалентностей можно убедиться путем построения таблиц соответствующих им функций.

Пример 1.1.1. По функциям f (x1, x2 ) и g(x1, x2 ), заданным векторно ~ ~ 1001, 1110, построить векторное задание функции f g h(~3) f (x1, g(x2, x3)) g(x2, f (x1, x3)).

x Решение. Для каждой из функций x1 x2 f (x1, x2 ) g(x1, x2 ) f (x1, x2 ) и g(x1, x2 ) перейдём от век0 0 1 торного задания к табличному (см. табл.

0 1 0 1.4).

1 0 0 1 1 1 В таблице 1.5 функция h(~3), реалиx зуемая заданной формулой, построена «постепенно». Табл. 1.4. Табличное задание функций Здесь используются следующие обозначения: g1 g(x2, x3), f1 f (x1, g1), f2 f (x1, x3 ), g2 g(x2, f2 ).

x1 x2 x3 g1 f1 f2 gh(~3) x 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 Табл. 1.5.

Процесс построения искомой функции Принимая во внимание тот факт, что функция x y равна нулю только на наборе (1,0), а функция g(x1, x2 ) равна нулю лишь на наборе (1,1), процедуру построения таблицы функции h(~3) можно упростить.

В самом деле, функция x h(~3) 0 тогда и только тогда, когда f (x1, g(x2, x3 )) 1 и g(x2, f (x1, x3)) 0.

x В свою очередь, g(x2, f (x1, x3)) 0 тогда и только тогда, когда x2 f (x1, x3 ) 1. В силу того, что f (x1, x3) 1 при x1 x3, заключаем, что g(x2, f (x1, x3)) 0 либо при x1 x2 x3 1, либо при x2 1, x1 x3 0.

Теперь f (x1, g(x2, x3 )) 1 тогда и только тогда, когда x1 g(x2, x3). Замечаем, что если x1 0, то g(x2,0) 1 при любом значении x2. Если x1 1, тогда g(x2,1) 1 при единственном значении переменной x2 0.

Получаем, что ~ h 11111111.

Соседними наборами по k-ой компоненте называются наборы ~ ~ (1,…,k1,0,k1,…,n ) и (1,…,k 1,1,k 1,…,n), различающиеся только в k-ой компоненте.

Переменная xk для функции f ( x1, x2,…, xn ) называется существенной, ес~ ~ ли найдется пара наборов и, соседних по k-ой компоненте, таких, что ~ ~ f f. В противном случае переменная xk называется несущественной или фиктивной.

Пусть для функции f ( x1, x2,…, xn ) переменная xk является фиктивной.

Возьмем таблицу, задающую функцию f ( x1, x2,…, xn ). Вычеркнем из нее все строки вида 1,…,k 1,1,k 1,…,n, f (1,…,k 1,1,k 1,…,n ), а также столбец, соответствующий переменной xk. Полученная таблица будет определять некоторую булеву функцию g( x1, x2,…, xk 1, xk 1,…, xn ) от n 1 переменной.

Будем говорить, что функция g( x1, x2,…, xk 1, xk 1,…, xn ) получена из функции f ( x1, x2,…, xn ) путем удаления фиктивной переменной xk, а также что функция f ( x1, x2,…, xn ) получается из g( x1, x2,…, xk 1, xk 1,…, xn ) путем введения фиктивной переменной xk.

n m n ~ ~ ~ Две функции f ( x ) и g( x ) называются равными, если функцию f ( x ) m ~ можно получить из функции g( x ) путем введения и удаления фиктивных переменных. Заметим, что для любой функции, отличной от константы 0 или 1, существует равная ей, у которой все переменные существенные.

Пример 1.1.2. Перечислить все существенные и фиктивные переменные у функции f (~3) 11110011.

x Решение. Рассмотрим таблицу значений функции f (~3) (табл.1.6).

x Сравнивая значения функции на всех парах наборов, соседних по переменной x3, отметим, что f 0,0,0 f 0,0,1 1, f 0,1,0 f 0,1,1 1, f 1,0,0 f 1,0,1 0 x1 x2 xf (~3) x и f 1,1,0 f 1,1,1 1. Получаем, что 0 0 0 f (x1, x2,0) f (x1, x2,1). Следовательно, пе0 0 1 0 1 0 ременная x3 фиктивная.

0 1 1 Строим функцию g(~2 ) посредством опеx 1 0 0 рации удаления из функции f (~3) фиктивной x 1 0 1 переменной x3 : вычеркнем из табл. 1.6 все 1 1 0 1 1 1 строки, соответствующие наборам вида (1,,1) и столбец, соответствующий переменной x3. Табл. 1.6. Функция f (~3 ) x В таблице 1.7 представлена полученная функция g(x1, x2 ).

Далее, так как g1,0 0, а g1,1 1, заключаx1 x2 g(x1, x2 ) ем, что переменная x2 существенная. Аналогично, 0 0 так как g0,0 1, а g1,0 0, то переменная x0 1 1 0 существенная. Итак, у функции f (~3) переменные x 1 1 x1 и x2 существенные, а переменная x3 фиктивная.

(Нетрудно убедиться в том, что f (~3) x1 x2.) Табл. 1.7. Функция g(~2 ) x x Задачи 1.1.1. По функциям f (x1, x2 ) и g(x1, x2 ), заданным векторно, построить функцию h :

~ ~ 1) 1011, 0111, f g а) h(~2 ) f (x1, g(x1, x2 ));

x б) h(~2 ) g(x2, f (x2, x1));

x в) h(~2 ) f ( f (x1, g(x1, x2)), g(x1, x2 ));

x г) h(~3) g(x1, x2) f (x3, g(x1, x2 ));

x д) h(~3) f (x2, g(x3, x1)) g(x1, g(x2, x3)).

x ~ ~ 2) 1010, 0110, f g а) h(~3) f (x3, g(x1, x2 ));

x б) h(~3) g(g(x3, x2), f (x1, x3));

x в) h(~3) f ( f (x3, g(x1, x2)), g(x1, x2 ));

x г) h(~3) f ( f (x1, x2), g(x3, x1)) g(x1, g(x1, x2)).

x 1.1.2. Доказать тождества:

1) x y x y y ;

2) x y x y& y x;

3) x y x x y y x x y y;

4) x y z x y x z;

5) x & y z x & y x & z x ;

6) x y z x y x z;

7) x y z x y x z;

8) x & y z x y x & z;

9) x y z x y x z;

10) x y & z x y& x z;

11) x y z x y x z.

1.1.3. Построив таблицы соответствующих функций, выяснить, эквивалентны ли формулы A и B:

1) A x y z x z x y, B x y y z x z z ;

y 2) A x y z x y z, B x y z x;

3) A x y z x y z, B x y z x y y x z;

4) A x y x z x y z x y, B x y z x ;

5) A x y z y y z, B x y y z x y z;

6) A x y zx yy z x, B x yy x;

7) A x y y z x z, B x y z x z;

8) A x y x zy z x y, B x y z y z ;

9) A x y y z x x z, B x y x x z;

y 10) A x x y x z y y z, B x y z ;

11) A x y z x z y x y z, B x y z x y ;

12) A x y x z x y z, B x z y;

13) A x y x z x y z, B x y z x z ;

14) A x y zx y zx y z, B x y y x z x (y z);

15) A x y z y z, B x x y zx y z;

16) A x y y z y x z x y z, B x y z.

1.1.4. Используя основные эквивалентности булевой алгебры, упростить формулы A и B из задачи 1.1.3.

1.1.5. Перечислить все существенные и фиктивные переменные у следующих функций:

1) f (~3) 10101010;

x 2) f (~3) 10011001;

x 3) f (~3) 00111100;

x 4) f (~4) 0101111101011111;

x 5) f (~ 4 ) 1100110000110011;

x 6) f (~ 4 ) 1011010110110101;

x 7) f (~2 ) x1 x2 x1 x2 x1 x2x2 x1;

x 8) f (~2 ) x1 x2 x1 x2 x1 x1 x2 ;

x 9) f (~3) x1 x2 x2 x3 x2 x3;

x 10) f (~3) x1 x2 x3 x2 x1 x3 x1 x3;

x 11) f (~3 ) x1 (x2 x3 ) x2 (x1 x3 ) (x1 x2 ).

x 1.1.6. Показать, что x1 – фиктивная переменная у функции f, реализовав для этой цели функцию f формулой, не содержащей явно переменную x1:

1) f (~2 ) x2 x1x2 x2;

x 2) f (~2 ) x1 x2 x1 x2;

x 3) f (~3) x1 x2 x3x3 x2 ;

x 4) f (~3) x1 x2 x3 x1 x2 x3x2 x3;

x 5) f (~3 ) x1 x2 x3 x1x2 x3 x2 x1 x3.

x 1.1.7. Найти число всех функций от n переменных, которые на противоположных наборах принимают одинаковые значения. При n = 2,3 найти все такие функции, существенно зависящие от всех переменных.

1.1.8. Найти число всех функций от n переменных, которые на противоположных наборах принимают противоположные значения. При n = 2,3 найти все такие функции, существенно зависящие от всех переменных.

1.1.9. Найти число всех функций от n переменных, которые на любой паре соседних наборов принимают противоположные значения. Найти вид этих функций.

Источник: http://knigi.dissers.ru/books/1/14393-1.php

«Нижегородский государственный университет им. Н.И.Лобачевского Л.Г. Киселева, Т.Г. Смирнова Функции алгебры логики в примерах и задачах Учебно-методическое пособие Рекомендовано методической …»

Функции алгебры логики в примерах и задачах. Киселева Л.Г

Нижегородский государственный университет им. Н.И.Лобачевского

Л.Г. Киселева, Т.Г. Смирнова

Функции алгебры логики

в примерах и задачах

Учебно-методическое пособие

Рекомендовано методической комиссией факультета вычислительной математики и

кибернетики для студентов ННГУ, обучающихся по направлениям подготовки

010500 «Прикладная математика и информатика»,

010400 «Информационные технологии»

Нижний Новгород УДК 519.95 ББК 22.174 К 44 К44 Киселева Л.Г., Смирнова Т.Г. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ В ПРИМЕРАХ И ЗАДАЧАХ: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2008. – 57 с.

Рецензент: д. физ.-мат. наук, проф., зав. каф. ИИТ НГПУ М.А. Иорданский В учебно-методическом пособии изучаются основные понятия и различные представления функций алгебры логики.

Особое внимание уделяется проблеме полноты систем булевых функций.

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

Учебно-методическое пособие предназначено для студентов факультета ВМК, изучающих общий курс “Дискретная математика”.

УДК 519.95 ББК 22.174 © Нижегородский государственный Университет им. Н.И. Лобачевского, 2008 Глава 1. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

1.1. Основные понятия и определения Пусть E 0,1. Набор (1, 2,…, n ), где i E, называется булевым или ~ двоичным набором и обозначается через n. Число n называется длиной набора n, а число единиц в наборе n – весом набора n. Каждому двоичному n ~ ~ ~ набору n можно сопоставить число ( n ) i 2 n i номер набора n.

i 1 ~ ~ Набор n является двоичным разложением своего номера ( n ).

E n – множество всех двоичных наборов длины n.

Функция f ( x1, x 2,…, x n ), определенная на множестве E n и принимающая значения из множества E, называется функцией алгебры логики или булевой n функцией от n переменных, т.е. f : E

–  –  –

Теорема 1.1.

1. Мощность P2 n множества всех булевых функций от n n переменных равна 2 2.

Доказательство. Так как функцию алгебры логики от n переменных можно задать упорядоченным двоичным набором длины 2 n, то число различных функций алгебры логики от n переменных равно числу всех двоичных наборов n длины 2 n, т.е. 2 2. Теорема доказана.

С ростом числа переменных таблица, задающая булеву функцию, сильно усложняется, становится громоздкой. Число функций от n переменных быстро растет: P2 1 4, P2 2 16, P2 3 256, P2 4 65536.

Рассмотрим теперь элементарные функции алгебры логики.

Имеются четыре булевы функции от одной переменной (см. табл. 1.2).

Эти функции носят соответственно следующие названия:

x x x 0 – константа нуль.

x – тождественная функция.

x – отрицание x, читается как «не x ».

1 – константа единица. Табл.1.2. Функции одной переменной

–  –  –

Приведенные в табл. 1.3 булевы функции от двух переменных носят следующие названия:

x & y – конъюнкция x и y, обозначается также x y или xy, читается «x и y».

x y – дизъюнкция x и y, читается «x или y».

x y – сложение по модулю 2 x и y, читается «x плюс y».

x y – импликация x и y, читается «из x следует y».

x y – эквивалентность x и y, часто обозначается как x ~ y, читается «x эквивалентно y».

x y — штрих Шеффера x и y, часто эта функция называется антиконъюнкцией, читается «не x или не y».

x y — стрелка Пирса x и y, часто эта функция называется антидизъюнкцией, читается «не x и не y».

, &,,,,,,, участвующие в обозначениях элеменСимволы тарных функций, называются логическими связками.

Суперпозицией булевых функций f1,…, f m называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных.

Формулой в алгебре логики называется всякое (и только такое) выражение вида:

1) x любая переменная из множества переменных X ;

2) ( F ), ( F1 F2 ), где F, F1, F2 произвольные формулы алгебры логики, а &,,,,,, логическая связка.

Обычно внешние скобки у формул не записываются. Обратим внимание, что связка отрицания сильнее, чем любая двухместная связка, а связка & самая сильная из связок,,,,,. Эти соглашения позволяют упрощать запись формул и не писать ряд скобок. Например, формула ((( x y ) & z ) (( x & z ) ( y & z ))) записывается как ( x y ) z ( xz yz ).

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

В отличие от табличного задания представление данной функции формулой не единственно.

Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными.

Рассмотрим далее некоторые эквивалентности, характеризующие свойства элементарных булевых функций.

–  –  –

1.1.7. Найти число всех функций от n переменных, которые на противоположных наборах принимают одинаковые значения. При n = 2,3 найти все такие функции, существенно зависящие от всех переменных.

1.1.8. Найти число всех функций от n переменных, которые на противоположных наборах принимают противоположные значения. При n = 2,3 найти все такие функции, существенно зависящие от всех переменных.

1.1.9. Найти число всех функций от n переменных, которые на любой паре соседних наборов принимают противоположные значения. Найти вид этих функций.

–  –  –

где дизъюнкция берётся по всем наборам ( 1,…, n ) из E n, на которых функция f ( ~ n ) обращается в единицу.

x Представление функции в виде (4) называется совершенной дизъюнктивной нормальной формой (сокращённо совершенной д.н.ф. или СДНФ) функции f ( ~ n ).

x Из представления функции в виде совершенной д.н.ф. и тождества 0 x x получаем следующее утверждение.

Теорема 1.2.

4. Всякую функцию алгебры логики можно представить в виде формулы через отрицание, конъюнкцию и дизъюнкцию.

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

Теорема 1.2.

5. Каждую булеву функцию f ( x1,…, x n ) при любом

k ( 1 k n ) можно представить в виде:

–  –  –

Представление функции в виде (7) называется совершенной конъюнктивной нормальной формой (сокращённо совершенной к.н.ф. или СКНФ) функции f ( ~ n ).

x

Источник: http://kniga.lib-i.ru/26informatika/214723-1-nizhegorodskiy-gosudarstvenniy-universitet-nilobachevskogo-kiseleva-smirnova-funkcii-algebri-logiki.php

Biz-books
Добавить комментарий