Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

Функционально полные системы логических функций. Алгебраический подход

Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники
Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Мыло металлическое "Ликвидатор".
Мыло для рук «Ликвидатор» уничтожает стойкие и трудно выводимые запахи за счёт особой реакции металла с вызывающими их элементами.
197 руб
Раздел: Ванная

Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» кафедра ЭТТ РЕФЕРАТ На тему: «Функционально полные системы логических функций. Алгебраический подход» МИНСК, 2008 Из множества функционально полных наборов рассмотрим только те, которые имеют наибольшее практическое значение. 1. Основная функционально полная система логических функций. Наибольшее распространение получил набор, в состав которого входят три логические функции: f10 – инверсия (логическая связь НЕ, логическое отрицание); f1 – конъюнкция (логическая связь И, логическое умножение), f7 – дизъюнкция (логическая связь ИЛИ, логическое сложение). Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально полная система логических функций является избыточной, так как условиям теоремы отвечают наборы функций f10 и f1 или f10 и f7. Свойства этих функций были рассмотрены ранее. Из определения представления переключательной функции в виде дизъюнктивной или конъюнктивной нормальной формы следует, что эти представления реализуются в основной функционально полной системе логических функций. 2. Законы алгебры логики в ОФПС и их следствия. В алгебре логики имеются четыре основных за­кона, регламентирующих порядок производства операций НЕ, И, ИЛИ в любом логическом выражении: переместительный (коммутативный); сочетательный (ассоциативный); распределительный (дистрибутивный); инверсии (правило Де Моргана). Переместительный закон. Этот закон справедлив как для дизъюнкции, так и для конъюнкции: x1 x2 = x2 x1; x1 Щx2 = x2 Щ x1. (1) Справедливость выражения (5.1) нетрудно доказать простой подста­новкой в него различных значений x1 и x2. Поскольку любую переста­новку большего количества слагаемых можно свести к последователь­ности перестановок слагаемых в отдельных парах, то переместитель­ный закон будет справедлив при любом числе слагаемых. Сочетательный закон. Этот закон, так же как и переместительный, является симметричным, т. е. справедливым и для дизъюнкции, и для конъюнкции: x1 x2 x3 = x1(x2 x3) = (x1 x2)x3= x2( x1 x3); (2) x1 Щx2 Щx3 = x1Щx2 Щx3) = (x1 Щx2)Щx3= x2Щ( x1 Щx3). Доказательство этого закона также не представляет никаких труд­ностей и может быть выполнено простой подстановкой. Распределительный закон. В отличие от обычной алгебры алгебра логики симметрична. В ней справедливы два распределительных закона: для логического умножения относительно логического сложения (рас­пределительный закон 1-го рода) и для логического сложения относи­тельно логического умножения (распределительный закон 2-го рода). 1. Распределительный закон 1-го рода записывается следующим образом: (x1x2)Щx3=(x1Щx3) ( x2 Щx3) . (3) Справедливость формулы (5.3), а также и ее более общего случая, когда в скобках заключена сумма любого количества слагаемых, можно доказать путем установления идентичности условий обращения в 0 или 1 ее левой и правой частей. Условием обращения в нуль левой части выражения (5.3) состоит в том, чтобы нулю равнялся либо один аргумент х3, либо одновременно аргументы x1 и x2.

Условия обращения в нуль правой части выражения (5.1) такие же. Следовательно, распределительный закон 1-го рода справедлив для алгебры логики. 2. Распределительный закон 2-го рода имеет вид (x1Щx2)x3=(x1x3)Щ ( x2x3). (4) Cправедливость формулы (4) (при любом количестве аргументов) нетрудно доказать посредством установления идентичности условий обращения обеих ее частей в единицу. Закон инверсии (правило Де Моргана). Этот закон, так же как и все предыдущие, симметричен относительно логических сложения и умножения. 1. Отрицание логической суммы нескольких аргументов равно ло­гическому произведению отрицаний этих же аргументов: (5) Доказательство закона не представляет трудностей, поскольку условие обращения в нуль как левой, так и правой частей выражения (5) состоит в том, чтобы был истинным хотя бы один аргумент. 2. Отрицание логического произведения нескольких аргументов равно логической сумме отрицаний этих же аргументов: (6) Справедливость этого закона следует из того, что условие обращения в единицу обеих частей формулы (6) заключается в том, чтобы был ложным хотя бы один аргумент. Следствия из законов алгебры логики. Из доказанных выше за­конов можно вывести ряд следствий, которые сформулируем в виде правил. Правило выполнения совместных логических действий (правило старшинства логических функций). При решении логических задач приходится встречаться с выражениями, содержащими действия отри­цания, конъюнкции и дизъюнкции в любом сочетании. По аналогии с арифметическими действиями будем считать отрицание логическим действием первой ступени (старшей логической опера­цией), конъюнкцию — действием второй ступени, а дизъюнкцию — действием третьей ступени (младшей логической операцией). Старшинство операции инверсии вытекает из закона инверсии, в соот­ветствии с которым логическая сумма отрицаний некоторых аргументов не равна отрицанию их суммы (это справедливо и для логического произведения). Это значит, что ни операцию дизъюнкции, ни операцию конъюнкции нельзя проводить, игнорируя знак отрицания над каким-либо из логических аргументов, т. е. операцию отрицания надо про­водить в первую очередь. Относительно операций логического сложения и умножения на основании симметричности законов алгебры логики можно сказать, что они «равноправны». Из этого следует, что можно условиться считать более старшей операцией любую из них, но, приняв какое-либо усло­вие, надо придерживаться его все время. На практике оказалось удоб­нее считать более старшей операцию логического умножения, так как это соответствует правилам обычной алгебры и для нас более привычно. На основе изложенного можно сформулировать следующее пра­вило выполнения совместных логических действий: если в логическом выражении встречаются только действия одной и той же ступени, то их принято выполнять в том порядке, в котором они написаны; если в логическом выражении встречаются действия различных ступеней, то сначала принято выполнять действия первой ступени, затем — второй, и только после этого — третьей. Всякое отклонение от этого порядка должно быть обозначено скобками.

Правило склеивания. Прежде чем сформулировать само правило, введем некоторые новые понятия. Если имеется некоторый конечный набор логических аргументов x1, x2, x , то логическое произведение любого их числа называется элементарным в том случае, когда сомножите­лями в нем являются либо одиночные аргументы, либо отрицания одиночных аргументов. Так, например, f1(х1, х2, x3, х4)= х1Ч х2Ч x3Чх4 — элементарное произведение (элементарная конъюнкция); —не является элементарным про­изведением. Cимвол любого аргумента в элементарной конъюнк­ции может встречаться только один раз, поскольку произведение аргу­мента самого на себя равно этому же аргументу, а произведение аргу­мента на свое отрицание равно нулю. Количество сомножителей в элементарной конъюнкции называется ее рангом. Два элементарных произведения одинакового ранга r называются соседними, если они являются функциями одних и тех же аргументов и отличаются только знаком отрицания (инверсии) одного из сомножи­телей. Например, элементарные конъюнкции f1(х1, х2, x3, х4)= х1Ч х2Ч x3Чх4 и f3(х1, х2, x3, х4)= являются соседними, так как отличаются только одной инверсией в переменной x2, а элементарные конъюнкции f3(х1, х2, x3, х4)= и f4(х1, х2, x3, х4)= соседними не являются. Правило склеивания для элементар­ных конъюнкций может быть сформулировано следующим образом: логическую сумму двух соседних произведений неко­торого ранга r можно заменить одним элементарным произведением ранга r-1, являющимся общей частью исходных слагаемых. Это правило является следствием распределительного закона 1-го рода и доказывается путем вынесения за скобку общей части сла­гаемых, являющихся соседними конъюнкциями. Тогда в скобках ос­тается логическая сумма некоторого аргумента и его инверсии, равная единице, что и доказывает справедливость правила. Например, . Поскольку алгебра логики является симметричной, то все опреде­ления, данные для конъюнкции, будут справедливы и для дизъюнкции. Если имеется некоторый конечный набор логических аргументов, то логическая сумма (дизъюнкция), зависящая от любого их числа, называется элементарной в том случае, когда слагаемыми в ней явля­ются либо одиночные аргументы, либо отрицания одиночных аргу­ментов. Количество слагаемых в элементарной дизъюнкции называется ее рангом. Две элементарные суммы одинакового ранга называются соседними, если они являются функциями одних и тех же аргументов и отлича­ются только знаком отрицания (инверсии) одного из слагаемых. Правило склеивания двух элементарных дизъюнкций формули­руется так: логическое произведение двух соседних сумм некоторого ранга r можно заменить одной элементарной суммой ранга r-1, являющейся общей частью исходных сомножителей. Это правило является следствием распределительного закона 2-го рода и применяется для упрощения логических выражений. Например: Правило поглощения. Так же как и склеивание, поглощение может быть двух видов. Правило поглощения для двух элементарных конъюнкций форму­лируется так: логическую сумму двух элементарных произведений раз­ных рангов, из которых одно является собственной частью другого, можно заменить слагаемым, имеющим меньший ранг.

Отсюда их исключительно широкое применение и развитие. С понятием полноты связано понятие операции замыкания и замкнутого класса. Пусть 9t c P • Множество всех функций, которые могут быть получены из функций системы 9t с помощью операции суперпозиции, называется замыканием 91 и обозначается [9t ]. Класс функций 9t называется (функционально) замкнутым, если [9t ] = 9t, т. е. замкнутость класса функций 9I обозначает собою сохранение при суперпозиции «наследственных» свойств этих функций. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: 9t — полная система, если [ 9t ] = Р . 587 МНОЖЕСТВ ТЕОРИЯ Сложной технической проблемой для n-значных логик остается распознавание полноты для произвольных систем. Выделяются два подхода к решению задачи о полноте. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту системы функций; во втором рассматривают совокупность всех предполных классов функций в Ря. Система Э{ функций называется предполной в Р, если 9? представляет не полную систему но добавление к SR любой функции f такой, что f Е Ря и f e 9( преобразует Э( в полную систему

1. Стандарты сотовой связи 1-го и 2-го поколений. Организация хэндовера

2. Отличия законов о рекламе и закона о защите прав потребителя

3. Алгебра логики

4. Минимизация функций алгебры логики

5. Закон рынка Сэя. Концепция непотребления Т.Мальтуса. И влияние на них налоговой системы.

6. Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций
7. Русская армия от Петра 1 до Александра 2
8. Использование численных методов для решения дифуpов (2-го порядка) (, демонстрация применения интерполяции в среде MATHCAD-а)

9. Поверхности 2-го порядка

10. Друга світова війна 1 вересня 1939 – 2 вересня 1945

11. Решения неоднородных дифференциальных уравнений 2-го порядка с постоянными коэффициентами. Комплексные числа

12. Дирижерско-хоровое отделение ГОУ СПО МО 2-го Московского областного музыкального училища имени С.С. Прокофьева

13. Сравнение основных законов мышления в формальной логике

14. Законы логики

15. Законы логики

16. Основные законы логики

Глобус Звездного неба диаметром 320 мм.
Диаметр: 320 мм. Масштаб: 1:40000000. Материал подставки: пластик. Цвет подставки: черный. Шар выполнен из толстого пластика, имеет один
1007 руб
Раздел: Глобусы
Набор детской складной мебели "Веселая азбука".
Детский комплект складной мебели подходит для кормления, игр и обучения. Поверхность столешницы ламинированная с нанесением ярких
1629 руб
Раздел: Наборы детской мебели
Набор мебели для кухни "Коллекция".
Прекрасный набор кухонной мебели: стильный шкаф с необходимой техникой, раковиной, барной стойкой и холодильник. В набор так же входит
963 руб
Раздел: Кухни, столовые

17. Основы и законы логики

18. Закон российской федерации о воинской обязанности и военной службе

19. Законность и правопорядок

20. Механизм применения антимонопольных законов

21. Понятие договора найма по Закону о договорных и внедоговорных обязанностях

22. Законы Хаммурапи – выдающийся памятник права Древнего Вавилона
23. Конституция - основной закон государства и общества. Конституционные акты российской государственности до октября 1917 г.
24. Уголовный закон Украины

25. Закон Украины «О гражданстве»

26. Конституция - основной закон государства

27. Конституция – основной закон государства. Основы конституционного строя

28. Структура закона Саратовской области "О местном самоуправлении в Саратовской области". Полномочия органов местного самоуправления в области жилищного хозяйства, коммунально-бытового и торгового обслуживания населения

29. Комментарий к Федеральному закону "Об информации, информатизации и защите информации"

30. Цели, задачи и структура Федерального закона № 122-ФЗ

31. Основные виды деликтов в законах XII таблиц

32. Действие закона во времени, в пространстве, по кругу лиц

Шар для принятия решений.
Волшебный шар для принятия решений на русском языке. Принцип действия: для начала нужно понять, на какой вопрос вы хотите получить ответ.
434 руб
Раздел: Прочее
Переносная люлька-кокон Фея, цвет: серо-голубая, арт: ФЕЯ_0005605-5.
Переносная люлька-кокон — это комфортная переноска для малыша. Модель с жестким дном и съемным капюшоном защитит ребенка от холода и
910 руб
Раздел: Переноски
Машинка детская с полиуретановыми колесами "Бибикар-лягушонок", оранжевый.
Вашему крохе едва исполнилось 3 годика, а он уже требует дорогой квадроцикл на аккумуляторе, как у взрослых соседских мальчишек? Никакие
2350 руб
Раздел: Каталки

33. Право и закон: грани соотношения

34. Конституция в киберпространстве: закон и свобода за электронной границей (english/russian)

35. Закон, живущий в нас, называется совестью

36. Лессинг: «О законах временных и пространственных видов искусств»

37. Комментарий к Федеральному закону "Об информации, информатизации и защите информации"

38. Определение законов распределения случайных величин и их числовых характеристик на основе опытных данных. Проверка статистических гипотез
39. Прокурорский надзор за исполнением законов органами, осуществляющими предварительное следствие и оперативно-розыскную деятельность
40. Прокурорский надзор за исполнением законов

41. Проблемы укрепления законности и правопорядка

42. Обратная сила закона. Теория и практика применения на примере преступлений против собственности

43. Уголовный закон: понятие, признаки, значение

44. Вопрос о действии промежуточного закона

45. Социальные законы экологии

46. Законы и категории диалектики в педагогической практике

47. ПУП в рамках закона и морали. Программа самой благозвучной партии России - партии умеренного прогресса

48. Психологический смысл психофизических законов

Игрушка "Музыкальная сова".
Музыкальная сова танцует и машет крылышками с мигающими огоньками! А ещё она рассказывает сказки: "Курочка Ряба",
653 руб
Раздел: Животные
Копилка "Яблоко".
Принцип работы: копилка "заглатывает" монетку положенную на "язычок". Присутствуют звуковые эффекты.
368 руб
Раздел: Копилки
Мешок для обуви "Синий", 33х40 см.
Мешок для обуви. Размер: 33х40 см.
315 руб
Раздел: Сумки для обуви

49. Изучение законов нормального распределения и распределения Релея

50. Второй Закон Термодинамики

51. Вероятностные или статистические законы

52. Динамические законы и механический детерминизм

53. История открытия закона Ома, виды закона Ома

54. Эвристические функции законов сохранения
55. Великие законы сохранения
56. Диалектика: принципы, законы, категории

57. Динамические законы и механический детерминизм

58. Логические законы

59. Теория стоимости. Закон стоимости и его функции

60. Количественный подход к анализу индивидуального спроса. Спрос и полезность. Закон убывающей предельной полезности, его значение

61. Структура организации, влияние на нее законов теории организации

62. Федеральный закон о бюджете на 2000 год

63. Сущность и функции денег. Закон денежного обращения. Инфляция

64. Общая и предельная полезность. Законы Госсена

Заварочный чайник "Mayer & Boch", 500 мл.
Заварочный чайник Mayer & Boch с металлическим фильтром изготовлен из термостойкого боросиликатного стекла. Крышка и ручка из пластика,
427 руб
Раздел: Чайники заварочные
Детский велосипед "Jaguar" трехколесный (цвет: оранжевый).
Детский трехколесный велосипед для малышей от 1 года до 3 лет. Трехколесный велосипед колясочного типа с музыкально-световой кнопкой.
1800 руб
Раздел: Трехколесные
Ежедневник. Гравити Фолз.
СУПЕРпроект самого крутого мультсериала во всем мире – Гравити Фолз! ЕжеДНЕВНИК станет отличным помощником в решении сложных задач,
370 руб
Раздел: Блокноты художественные

65. Рынок и закон спроса

66. Законы Хаммурапи

67. Положение воинов по законам царя Хаммурапи

68. Свод Законов Российской империи 1825 г.

69. Закон Ленца

70. Слово о законе и благодати
71. Сон "есть закон природы, которого не знаем мы и который кричит в нас" (по роману Ф. М. Достоевского "Преступление и наказание")
72. Виникнення науки и поняття логічного закону

73. Основные законы правильного мышления

74. Относительность закона Хаббла

75. Закон Хаббла

76. Планеты и законы их обращения

77. Газовые законы в живой природе и медицине

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

79. Неинерциальные полевые принципы формирования структуры материи. Закон динамической гравитации

80. Закон всемирного тяготения

Велобег "Slider" с ручным тормозом (цвет: матовый черный, 12").
Беговел от бренда Slider матового черного цвета привлечет внимание ребенка и понравится ему благодаря современному стильному дизайну.
2779 руб
Раздел: Беговелы
Набор "Юный конструктор № 1", 137 деталей.
Все детали выполнены из прочного и качественного пластика и соединяются между собой при помощи болтов. Из деталей ребёнок сможет собрать
461 руб
Раздел: Воздушный транспорт
Съемный чехол для матраса Зёвушка "Фабрика облаков" (simple).
Съемный чехол на резинке из легкой ткани "Simple" предназначен к детскому матрасу "Зёвушка". Чехол изготовлен из
467 руб
Раздел: Наматрасники

81. Галилей и законы движения

82. Закон України Про зовнішньоекономічну діяльність

83. Билеты по предмету Организация торговли продовольственными и непродовольственными товарами. 1 семестр 2001-го.

84. Закон соответствия уровня потребления уровню выживания

85. Закон о налоговой службе Украины

86. Законы электролиза Фарадея
87. Закон сохранения момента импульса
88. Закон Снеллиуса

89. Законы сохранения в ядерных реакциях

90. Закон Авогадро

91. Комментарии к закону о «Невозобновляемых источниках энергии»

92. Уточненный закон всемирного тяготения Ньютона

93. Закон вечности

94. Основные законы химии

95. Законы сохранения

96. Закон всемирного тяготения

Термо ланч-бокс "Bento" (арт. TK 0049).
Термо ланч-бокс "Бенто" предназначен для тех, кто ценит комфорт при обеде, но не обладает большим количеством времени. Быстро
617 руб
Раздел: Штучно
Зеркальце карманное "Котик", 8x7 см.
Симпатичное карманное зеркало станет Вашим незаменимым помощником и с легкостью разместится даже в небольшой женской сумочке или кармане.
354 руб
Раздел: Зеркала, расчески, заколки
Коробка подарочная "Цветы и павлиньи перья".
Коробка подарочная. Материал: мелованный, ламинированный, негофрированный картон плотностью 1100 г/м2. Отделка: полноцветный декоративный
302 руб
Раздел: Коробки

97. Принцип эквивалентности и законы сохранения

98. Законы науки

99. Нарушаемость физических законов сохранения: философская апробация и научная перспектива

100. Формирование познавательного интереса школьников при изучении темы "Законы сохранения в механике"


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.