АХМЕТОВА Наиля Абдулхамитовна

Стр 1 из 12Следующая ⇒

АХМЕТОВА Наиля Абдулхамитовна

УСМАНОВА Зинира Масгутовна

Дискретная математика

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

Учебное пособие

Редактор Г.Р. Орлова

ЛР №020258 от 08.01.98

Подписано в печать 10.02.2000г. Формат 80х64 1/16

Бумага писчая. Печать плоская. Гарнитура «Таймс».

Усл. печ. 7, 9. Усл. кр.-отт. 7, 9. Уч.-изд.л. 7, 8.

Тираж 100 экз. Заказ №. С(3).

Уфимский государственный авиационный технический университет

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Задачи по комбинаторике

1. Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из одиннадцати дисциплин.

Ответ: 55 440.

2. Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределять между собой обязанности?

Ответ: 42.

3. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

Ответ: 1 140.

4. Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти звуков?

Ответ: 968.

5. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

Ответ: 253.

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

Ответ: 64.

7. Чемпионат, в котором участвуют 16 команд, проводится в два круга (т.е. каждая команда дважды встречается с любой другой). Определить, какое количество встреч следует провести.

Ответ: 240.

8. Замок открывается только в том случае, если набран определенный трехзначный номер. Попытка состоит в том, что набирают наугад три цифры из заданных пяти цифр. Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?

Ответ: 124.

9. Из группы в 15 человек выбирают четырех участников эстафеты 800+400+200+100. Сколькими способами можно расставить спортсменов по этапам эстафеты?

Ответ: 32 760.

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

Ответ: 25! /20!.

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

Ответ: 3 126.

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

Ответ: 896.

13. Порядок выступления восьми участников конкурса определяется жребием. Сколько различных исходов жеребьевки при этом возможно?

Ответ: 8!.

14. Тридцать человек разбиты на три группы по десять человек в каждой. Сколько может быть различных составов групп?

Ответ: 30! /(10! ) .

15. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

Ответ: 42.

16. Сколько различных светящихся колец можно сделать, расположив по окружности 10 разноцветных лампочек (кольца считаются одинаковыми при одинаковом порядке следования цветов)?

Ответ: 9!.

17. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?

Ответ:

18. Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?

Ответ: 2 520.

19. Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

Ответ: 12! /(2! ) .

20. Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5, содержат цифру 3 (цифры в числах не повторяются )?

Ответ: 204.

21. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы №1 и №2 находились бы в соседних аудиториях?

Ответ: 2× 9!.

22. В турнире участвуют 16 шахматистов. Определить количество различных расписаний первого тура (расписания считаются различными, если отличаются участниками хотя бы одной партии; цвет фигур и номер доски не учитываются).

Ответ: 2 027 025.

23. Шесть ящиков различных материалов доставляются на пять этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких вариантах на пятый этаж доставлен какой-либо один материал?

Ответ: 5⁶; 6× 4⁵.

24. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?

Ответ: 2¹⁰.

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

Ответ: 16¹⁰⁰.

26. Сколько трехзначных чисел, делящихся на 3, можно составить из цифр 0, 1, 2, 3, 4, 5, если каждое число не должно содержать одинаковых цифр?

Ответ: 40.

27. Собрание из 80 человек избирает председателя, секретаря и трех членов ревизионной комиссии. Сколькими способами это можно сделать?

Ответ: 80! (3! × 75! ).

28. Из 10 теннисисток и 6 теннисистов составляют 4 смешанные пары. Сколькими способами это можно сделать?

Ответ: 10! /48.

29. Три автомашины №1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов и если две машины в один и тот же магазин не направляются? Сколько вариантов маршрута возможно, если решено использовать только машину №1?

Ответ: 3⁶× 6!.

30. Четверо юношей и две девушки выбирают спортивную секцию. В секцию хоккея и бокса принимают только юношей, в секцию художественной гимнастики – только девушек, а в лыжную и конькобежную секции – и юношей, и девушек. Сколькими способами могут распределиться между секциями эти шесть человек?

Ответ: 2304.

31. Из лаборатории, в которой работает 20 человек, 5 сотрудников должны уехать в командировку. Сколько может быть различных составов этой группы, если начальник лаборатории, его заместитель и главный инженер одновременно уезжать не должны?

Ответ: 15 368.

32. В фортепьянном кружке занимаются 10 человек, в кружке художественного слова –15, в вокальном кружке – 12, в фотокружке – 20 человек. Сколькими способами можно составить бригаду из четырех чтецов, трех пианистов, пяти певцов и одного фотографа?

Ответ: 15! 10/7!

33. Двадцать восемь костей домино распределены между четырьмя игроками. Сколько возможно различных распределений?

Ответ:

34. Из группы в 15 человек должны быть выделены бригадир и 4 члена бригады. Сколькими способами это можно сделать?

Ответ: 15 015.

35. Пять учеников следует распределить по трем параллельным классам. Сколькими способами это можно сделать?

Ответ: 3⁵.

36. Лифт останавливается на 10 этажах. Сколькими способами могут распределиться между этими остановками 8 пассажиров, находящихся в лифте?

Ответ: 10⁸.

37. Восемь авторов должны написать книгу из шестнадцати глав. Сколькими способами возможно распределение материала между авторами, если два человека напишут по три главы, четыре – по две, два – по одной главе книги?

Ответ: 16! /(2⁶× 3²).

38. В шахматном турнире участвуют 8 шахматистов третьего разряда, 6 – второго и 2 перворазрядника. Определить количество таких составов первого тура, чтобы шахматисты одной категории встречались между собой (цвет фигур не учитывается).

Ответ: 420.

39. Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 составляются всевозможные пятизначные числа: не содержащие одинаковых цифр. Определить количество чисел, в которых есть цифры 2, 4 и 5 одновременно.

Ответ: 1800.

40. Семь яблок и два апельсина надо положить в два пакета так, чтобы в каждом пакете был хотя бы один апельсин и чтобы количество фруктов в них было одинаковым. Сколькими способами это можно сделать?

Ответ: 105.

41. Буквы азбуки Морзе состоят из символов (точек и тире). Сколько букв можно изобразить, если потребовать, чтобы каждая буква содержала не более пяти символов?

Ответ: 62.

42. Номер автомобильного прицепа состоит из двух букв и четырех цифр. Сколько различных номеров можно составить, используя 30 букв и 10 цифр?

Ответ: 9× 10⁶.

43. Садовник должен в течение трех дней посадить 10 деревьев. Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?

Ответ: 36.

44. Из вазы, где стоят 10 красных и 4 розовых гвоздики, выбирают один красный и два розовых цветка. Сколькими способами это можно сделать?

Ответ: 60.

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

Ответ: 2(6! )².

46. Каждый из десяти радистов пункта А старается установить связь с каждым из двадцати радистов пункта Б. Сколько возможно различных вариантов такой связи?

Ответ: 2²⁰⁰.

47. Шесть ящиков различных материалов доставляют на восемь этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких вариантах на восьмой этаж будет доставлено не более двух материалов?

Ответ: 8⁶; 8⁶–13× 7⁵.

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

Ответ: 2(11! )².

49. На книжной полке книги по математике и по логике – всего 20 книг. Показать, что наибольшее количество вариантов комплекта, содержащего 5 книг по математике и 5 книг по логике, возможно в том случае, когда число книг на полке по каждому предмету равно 10.

Ответ: C⁵_10–_x× C⁵₁₀₊_x(C⁵₁₀)².

50. Лифт, в котором находятся 9 пассажиров, может останавливаться на десяти этажах. Пассажиры группами выходят по два, три и четыре человека. Сколькими способами это может произойти?

Ответ: 10! /4.

51. «Ранним утром на рыбалку улыбающийся Игорь мчался босиком». Сколько различных осмысленных предложений можно составить, используя часть слов этого предложения, но не изменяя порядка их следования?

Ответ: 23.

52. В шахматной встрече двух команд по 8 человек участники партий и цвет фигур каждого участника определяются жеребьевкой. Каково число различных исходов жеребьевки?

Ответ:

53. A и B и еще 8 человек стоят в очереди. Сколькими способами можно расположить людей в очереди, чтобы A и B были отделены друг от друга тремя лицами?

Ответ: 6 × 8! × 2!.

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

Ответ: а) 5 × 5 × 4 × 3=300; б) 5 × 6 = 1080; в) 3⁴; г) 5 × 6 × 6 × 3 = 540.

55. В классе изучается 10 предметов. Сколькими способами можно составить расписание на понедельник, если в понедельник должно быть 6 уроков и все разные?

Ответ:

56. На одной прямой взято m точек, на параллельной ей прямой n точек. Сколько треугольников с вершинами в этих точках можно получить?

Ответ:

57. Сколько есть пятизначных чисел, которые читаются одинаково справа налево и слева направо, например, 67876.

Ответ: 9 × 10 × 10 = 900.

58. Сколько разных делителей (включая 1 и само число) имеет число

3⁵ × 5⁴?

Ответ: 30.

59. В прямоугольной матрице A = {a_ij} m строк и n столбцов. Каждое a_ijÎ {+1, –1}, причем произведение a_ij по любой строке или любому столбцу равно 1. Сколько таких матриц?

Ответ: 2^{(m–1)(n–1)}.

60. В комнате n лампочек. Сколько разных способов освещения комнаты,

при которых горит:

а) ровно k лампочек (k < n);

б) хотя бы одна лампочка.

Ответ: а) ; б) = 2n–1.

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

Ответ: = 126.

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

Ответ: = 210.

63. Имеется p белых и q черных шаров. Сколькими способами их можно выложить в ряд, чтобы никакие 2 черных шара не лежали рядом (q £ p + 1)?

Ответ: .

64. Имеется p разных книг в красных переплетах и q разных книг в синих переплетах (q £ p + 1). Сколькими способами их можно расставить в ряд, чтобы никакие две книги в синих переплетах не стояли рядом?

Ответ: .

65. Сколькими способами можно упорядочить {1, 2, ... n} чисел так, чтобы числа 1, 2, 3 стояли рядом в порядке возрастания?

Ответ: (n – 2)!.

66. На собрании должны выступить 4 докладчика: A, B, C и D, причем B не может выступить раньше A. Сколькими способами можно установить их очередность.

Ответ: 12 = 3! + 2× 2 +2.

67. Сколькими способами m + n + s предметов можно распределить на 3 группы, чтобы в одной группе было m предметов, в другой – n, в третьей – s предметов.

Ответ:

68. Сколько целых неотрицательных решений имеет уравнение x1+ x2+... + xm= n.

Ответ: .

69. Найти число векторов Z = (a1a2... an), координаты которых удовлетворяют условиям:

1) aiÎ {0, 1};

2) aiÎ {0, 1, ... k – 1};

3) aiÎ {0, 1, ... ki– 1};

4) aiÎ {0, 1} и a1+ a2+... + an= r.

Ответ: 1) 2n; 2) kn; 3) k1k2... kn; 4) .

70. Каково число матриц {aij}, где aijÎ {0, 1} и в которой m строк и n столбцов? 1) строки могут повторяться; 2) строки попарно различны.

Ответ: 1) 2m× n; 2) .

71. Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r элементов одного сорта и s другого.

Ответ: .

72. Сколькими способами число n можно представить в виде суммы k натуральных слагаемых (представления, различающиеся лишь порядком слагаемых считаются разными).

Ответ: .

73. Бросаются 10 одинаковых игральных костей. Сколькими способами они могут упасть так, что:

1) ни на одной кости не выпадет 6 очков;

2) хотя бы на одной кости выпадет 6 очков;

3) ровно на 3-х костях выпадет 6 очков;

4) ровно на 3-х костях выпадет 6 очков, на 2-х других выпадет 5 очков.

Ответ: 5¹⁰, 6¹⁰-5¹⁰, 24´ 5⁸, 630´ 4⁶

74. Считая, что телефонные номера состоят из 7 цифр, причем могут начинаться и с 0 тоже, найти число телефонных номеров, таких что:

1) 4 последние цифры одинаковы и не встречаются среди первых 3-х (первые 3 цифры различны.);

2) все цифры различны;

3) номер начинается с цифры 5;

4) номер содержит три цифры 5, две цифры 1 и две цифры 2.

Ответ: 5040, , 10⁶, 210.

75. 10 человек, среди которых Иванов и Петров, размещаются в гостинице в двух 3-х местных и в одном 4-х местном номерах. Сколькими способами они могут быть размещены? Сколькими способами их можно разместить, если Иванов и Петров помещены в 4-х местный номер?

Ответ: 4200, 560.

76. 52 карты раздаются 4-м игрокам, каждому по 13 карт. Сколькими способами их можно раздать, если

1) каждый игрок получит туза;

2) один из игроков получит все 13 карт единой масти;

3) все тузы попадут к одному из игроков;

4) 2 определенных игрока не получат ни одного туза.

Ответ: , , , .

77. Регистр калькулятора содержит 8 разрядов. Сколько будет 8-ми значных чисел, если

1) регистр содержит ровно 2 одинаковые цифры;

2) регистр содержит ровно 2 пары одинаковых цифр;

3) регистр содержит ровно 3 одинаковые цифры;

4) регистр содержит не более 3-х различных цифр.

Ответ: , , , .

78. Сколькими способами можно выстроить 9 человек:

1) в колонну по одному;

2) в колонну по 3, если в каждой шеренге люди выстраиваются по росту и нет людей одинакового роста?

Ответ: 9!, .

79. Из n букв, среди которых a встречается α раз, буква b встречается β раз, а остальные буквы попарно различны, составляются слова. Сколько среди них будет различных r-буквенных слов, содержащих h раз букву a и k раз букву b?

Ответ: .

80. Имеется колода из 4n (n³ 5) карт, которая содержит карты 4-х мастей по n карт каждой масти, занумерованных числами 1, 2…n. Подсчитать, сколькими способами можно выбрать 5 карт так, что среди них окажутся:

1) 5 последовательных карт одной масти;

2) 4 карты из 5-ти с одинаковыми номерами;

3) 3 карты с одним номером и 2 карты с другим;

4) 5 карт одной масти;

5) 5 последовательно занумерованных карт;

6) 3 карты из 5-ти с одним и тем же номером;

7) не более 2-х карт каждой масти.

Ответ: 4(n–4), 4n(n–1), 12n(n–1), , 4⁵(n–4), , .

81. Сколькими способами можно расставить n нулей и k единиц так, чтобы между любыми 2-мя единицами находилось не менее m нулей?

Ответ: .

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

Пример 2.

Рассмотрим несколько функций двух переменных

x₁	x₂	(x₁& x₂)	f₃	f₁₅

Покажем, что (х₁& x₂) существенно зависит от х₁. Рассмотрим наборы (0, 1) и (1, 1), здесь a₂=1, f(0, a₂)=0 и не равно f(1, a₂)=1. Покажем, что х₂ тоже существенная переменная. Рассмотрим наборы (1, 0) и (1, 1). Здесь a₁=1, f(1, 0)=0 и не равно f(1, 1)=1. Для функции f₃(x₁, x₂) покажем, что х₂– иктивная переменная, т.е. надо показать, что не существует наборов (a₁, 0) и (a₁, 1) таких, что f₃(a₁, 0)¹ f₃(a₁, 1). Пусть a₁=0, т.е. рассмотрим наборы (0, 0) и (0, 1), f(0, 0)=f(0, 1)=0. Пусть a₁=1, но f(1, 0)=f(1, 1)=1.

Для функции f₁₅ и x₁ и x₂ являются фиктивными переменными. x₁– фиктивная переменная, если не существует наборов (0, a₂) и (1, a₂), таких, что f(0, a₂)¹ f(1, a₂). Если a₂=0, то f(0, 0)=f(1, 0)=1. Пусть a₂=1, тогда f(0, 1)=f(1, 1)=1.

Пусть х_i является фиктивной переменной для функции f(x₁, ..., x_i, ..., x_n). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида: (a₁, ...a_i–₁, 1, a_i₊₁, ...a_n) или, наоборот, все строки вида: (a₁, ..., a_i–₁, 0, a_i₊₁, ...a_n) и столбец для переменной х_i. При этом получим таблицу для некоторой функции g(x₁, ..., x_i_–1, x_i₊₁, ...x_n). Будем говорить, что функция g(x₁, ...x_i_–1, x_i₊₁, ...x_n) получена из функции f(x₁, ..., x_i, ...x_n) путем удаления фиктивной переменной х_i или f получена из g путем введения фиктивной переменной х_i.

Определение 4 . Функции f₁ и f₂ называются равными, если f₂ можно получить из f₁ путем добавления или удаления фиктивной переменной.

Пример 3.

x₁	x₂	f₃

Вычеркнули строки типа (a, 1), т.е. (0, 1) и (1, 1) и столбец для х₂.

Получили f₃(x₁ x₂) = g(x₁) = x₁.

Пример 4.

x₁	x₂	g

Пусть функция g(x₁ x₂) задана таблицей и существенно зависит от обеих переменных. Построим функцию f(x₁, x₂, x₃), которая получается из g(x₁, x₂) введением фиктивной переменной х₃:

x₁	x₂	x₃	f

К наборам (х₁, х₂) мы добавим х₃=0, получим наборы вида: (a₁, a₂, 0), на этих наборах функцию f положим равной g(a₁, a₂), затем добавим наборы вида (a₁, a₂, 1), функцию f(a₁, a₂, 1) положим равной g(a₁, a₂).

Особую роль играют константы 0 и 1, которые не имеют существенных переменных и которые можно рассматривать как функции от пустого множества переменных.

2.2. Формульное задание функций алгебры логики

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении n-го дифференциала dⁿf(x): было введено понятие первого дифференциала df(x), а затем n-й дифференциал определялся как первый дифференциал от d^(n–1)f(x).

Определение 1. Пусть МÌ P₂, тогда:

1) каждая функция f(x₁, ..., x_n)Î M называется формулой над M;

2) пусть g(x₁, ..., x_m)Î M, G₁, ..., G_m – либо переменные, либо формулы над M. Тогда выражение g(G₁...G_n) – формула над M.

Формулы будем обозначать заглавными буквами: N[f₁, ..., f_s], имея в виду функции, участвовавшие в построении формулы, или N(х₁, ..., x_k) имея в виду переменные, вошедшие в формулу. G_i – формулы, участвовавшие в построении g(G₁, ..., G_n), называются подформулами.

Пример 1. Пусть N={(x₁& x₂), (x₁Ú x₂), (`x )}, тогда ((х₁& х₂)Ú х₃) – формула над N.

Сопоставим каждой формуле N(x₁, ..., x_n) функцию f(x₁, ..., x_n)Î P₂. Сопоставление будем производить в соответствии с индуктивным определением формулы.

1) Пусть N(x₁, ..., x_n)=f(x₁, ..., x_n), тогда формуле N(x₁, ..., x_n) сопоставим функцию f(x₁, ..., x_n).

2) Пусть N(x₁, ..., x_n)=g(G₁, ..., G_m), где каждое G_i – либо формула над M, либо переменная, тогда по индуктивному предположению каждому G_i сопоставлена либо функция f_iÎ P₂, либо переменная х_i, которую можно считать тождественной функцией. Таким образом, каждой формуле G_i сопоставлена функция f_i( ), причем: { }Í {x₁, ..., x_n}, т.к. в формуле N(x₁, ..., x_n) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции f_i зависят от переменных (x₁, ..., x_n), причем какие-то переменные могут быть фиктивными. Тогда N(x₁, ..., x_n) = g(G₁, ..., G_m) = g( f₁(x₁, ..., x_n), ..., f_m(x₁,.., x_n)). Сопоставим этой формуле функцию h(x₁, ..., x_n) следующим образом: пусть (a₁, ..., a_n) – произвольный набор переменных (x₁, ..., x_n). Вычислим значение каждой функции f_i на этом наборе, пусть f(a₁, ..., a_n)=b_i, затем найдем значение функции g(x₁, ..., x_m) на наборе (b₁, ..., b_m) и положим h(a₁, ..., a_n) = g(b₁, ..., b_m) = g(f₁(a₁, ..., a_n), ..., f_m(a₁, ..., a_n)). Так как каждое f_i(x₁, ..., x_n) есть функция, то на любом наборе (a₁, ..., a_n) она определяется однозначно, g(x₁, ..., x_m) – тоже функция, следовательно, на наборе (b₁, ..., b_n) она определяется однозначно, где h(x₁, ..., x_n) есть функция, определенная на любом наборе (a₁, ..., a_n).

Множество всех формул над M обозначим через < M>.

Определение 2. Две формулы N и D из < M> называются равными N=D или эквивалентными N~D, если функции, реализуемые ими, равны.

Пример 2. Доказать эквивалентность формул:

( & (х₂Å x₃))~( ).

x₁	x₂	x₃	x₂Å x₃	&	x₂ x₃	x₃ x₂	&	Ú x₁

Упрощение записи формул:

1) внешние скобки можно отпускать;

2) приоритет применения связок возрастает в следующем порядке: ~, , Ú, &;

3) связка – над одной переменной сильнее всех связок;

4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;

5) если нет скобок, то операции ~ и выполняются в последнюю очередь.

Принцип двойственности

Определение 1 . Функции f*(x₁, ..., x_n) называется двойственной к функции f(x₁, ..., x_n), если f*(x₁, ..., x_n) = ( ₁, ..., _n).

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:

x	f	f*

Функции f(x) = x и g(x) = двойственны сами себе:

x	f	f*	g	g*

так как f*(0)= (1).

Определение 2 . Если f*(x₁, ..., x_n) = f(x₁, ..., x_n), то f(x₁, ..., x_n) называется самодвойственной.

Пример 2. Покажем, что f(x₁, x₂, x₃)=x₁Å x₂Å x₃– самодвойственна:

x₁	x₂	x₃	f	f*

Если f*– самодвойственна, то ( ₁, ..., _n) = f(x₁, ..., x_n), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 3. Покажем, что функция х₁Ú х₂двойственна к x₁& x₂, функция х₁ х₂ двойственна к функции x₁|x₂.

x₁ x₂	f=х₁Ú х₂	f*	g=x₁\|x₂	g*=x₁ x₂
0 0 0 1 1 0 1 1

Теорема о двойственных функциях

Если f* двойственна к f, то f двойственна к f*.

Доказательство. f*(x₁, ..., x_n) = ( ₁, ..., _n). Найдем двойственную функцию к f*, т.е. (f*( x₁, ..., x_n))* = ( ( ₁, ..., _n))* = ( ₁, ..., _n) = f(x₁, .., x_n).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

Принцип двойственности

Теорема: Пусть функция h(x₁, ..., x_n) реализована формулой h(x₁, ..., x_n) = =g(G₁, ..., G_m) = g(f₁(x₁, ..., x_n), ..., f_m(x₁, ..., x_n)), где какие-то переменные могут быть фиктивными. Тогда h*( x₁, ..., x_n) = g*(f₁*( x₁, ..., x_n), ..., f_m*(x₁, …, x_n)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Доказательство . h*(x₁, ..., x_n) = ( ₁, ..., _n) = (f₁( ₁, ..., _n), ..., f_m( ₁, ..., _n)) = ( ₁( ₁, ..., _n), ..., ( ₁, ..., _n)) = g(( ), ..., (( ) = g*(f₁*( x₁, ..., x_n), ..., f_m*( x₁, ..., x_n)), что и требовалось доказать.

Если функция h(x₁, ..., x_n) реализуется формулой N[f₁, ..., f_n], то формулу, полученную из N заменой f_i, входящих в нее, на f_i* и реализующую функцию h*(x₁, ..., x_n), будем называть двойственной и обозначать N*(x₁, ..., x_n).