metod_15.03.04_atppp_moas_2016 (1016590)
Текст из файла
МИНОБРНАУКИ РОССИИФедеральное государственное бюджетное образовательное учреждение высшего образования«Московский технологический университет»МИРЭАСОГЛАСОВАНОУТВЕРЖДАЮУчебно-методический советДиректор Института информационныхИнститута информационных технологийтехнологий____________________«____» ______________ 2016 г.____________________А.С. Зуев«____» ______________ 2016 г.Математические основы автоматизированных системУЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕСоставитель Каширская Е.Н.Москва 2016ДАлгебра логикиВысказывания и операции над нимиВысказывание – это повествовательное предложение, о котором можносказать истинно оно или ложно.
Рассмотрим следующие предложения.Исходным понятием логики высказываний является простое высказывание. Это понятие не определяется через другие понятия, так как является базовым. Под высказыванием обычно понимают всякое повествовательно предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание называют истинным. В противном случае – ложным.Обычно элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными.
Истинные значения обозначаются буквой И или 1, а ложные – Л или 0.Из элементарных высказываний можно составить более сложные спомощью логических связок , , , , , называемых соответственно отрицание, логическое и (конъюнкция), логическое или (дизъюнкция), логическое следствие (импликация), эквивалентность и круглых скобок (, ). Семантику логических связок можно представить с помощью таблицы истинности. В левой частиэтой таблицы перечисляются все возможные комбинации значений логическихпеременных.
В правой части – соответствующие им значения новых выражений,полученных из переменных и связок.Хуххух уух ху0010011011011010001001101111Связки имеют следующий приоритет: . Приоритет операций,представленных логическими связками можно изменить с помощью скобок. Высказывания, построенные с помощью простых высказываний, связок и скобок,называют правильно построенными формулами или сокращённо формулами.Замечательным свойством логики высказываний является то, что ее семантика близка к соответствующим высказываниям на естественном языке. Так,например семантика формул содержащих связки и практически совпадает сосмыслом фраз содержащих слова «не» и «и».
Однако имеются и некоторые различия. Так формула х у несколько шире, чем русское «х или у». Выражение «хили у» по смыслу ближе к формуле х у х у. Еще больше различий междусемантикой формулы х у в логике высказываний и выражению «из х следуету». В русском языке это выражение истинно, если истинны х и у, т.е. предложение русского языка по смыслу совпадает с формулой х у.
Логическое следствиеистинно также, если х и у ложны или х ложна, а у истинна. Логическую формулух у следует интерпретировать на естественном языке так: «Если х истинна, тоу тоже истинна, а остальное неизвестно».Для любой формулы также можно построить таблицу истинности. Например, для формулы таблица истинности будет выглядеть следующим образом:хуxух х( x у) x ( x у)x001111011111100001110001Очевидно, что если формула содержит n переменных, то в таблице истинности будет содержаться 2n строк. В приведенном примере формула содержит 2переменные и 22 = 4 строки.
Кроме того, данная формула истинна на любомнаборе значений своих переменных. Такие формулы называются тождественноистинными или тавтологиями. В противоположной ситуации, формула явля-ется тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такиеформулы называют равносильными. Равносильные формулы будем обозначатьзнаком равенства =.Построение таблиц истинностиЗадание: по заданным формулам строить таблицы истинности.Задание № 1. Для функции, заданной своими истинностными значениями,постройте таблицу истинности.1)f(x, y, z) = ( 1, 0, 1, 0, 0, 1, 1, 0 ).2)f(x, y, z) = ( 0, 1, 1, 1, 0, 0, 0, 1).3)f(x, y, z) = ( 1, 1, 1, 0, 0, 0, 1, 1 ).4)f(x, y, z) = ( 0, 0, 1, 1, 0, 1, 1, 0 ).Задание № 2. Для функции, заданной формулой, постройте таблицу истинности.1)[( AB C ) B(C A B)]2)[( B C A) B] [( B A C ) ( BC A)].3)[( BC A) C ] A(C B)4)( A B C ) [( A B C ) B( A C )]Булевы функции.Законы алгебры логикиВ логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний.
Основными законамиявляются следующие: законы идемпотентности:oxx=xoxx=x x1=x x1=1 x0=0 x0=x x x = 0 – закон противоречия x x = 1 – закон исключения третьего x = x – закон снятия двойного отрицания законы поглощенияox (y x) = xox (y x) = xДоказательство этих и последующих законов элементарно осуществляетсяс помощью построения таблиц истинности или простейших логических рассуждений.Следующая группа законов представляет взаимосвязь между логическимиоперациями: (x y) = (x y) (y x) xy=xy законы Де Морганаo (y x) = y xo (y x) = y xЗамечательным следствием приведенных выше законов является следующий факт.
Любую логическую формулу можно заменить равносильной ей, носодержащую только две логические операции: конъюнкцию или отрицание илидизъюнкцию или отрицание. Дальнейшее исключение логических операций,очевидно, невозможно, то есть приведенные пары представляют минимальныйбазис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Этаоперация получила название «штрих Шеффера» и определяется следующим образом:хух|у001011101110На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок: x= x|x x y = (x | y) | (x | y)Также следует отметить, что x | y = (x y).К основным законам алгебры логики также относятся следующие: коммутативные законыoхy=yхoхy=yх дистрибутивные законыoх (y z) = (х y) (х z)oх (y z) = (х y) (х z) ассоциативные законыoх (y z) = (х y) zoх (y z) = (х y) zЕще одним важным законом алгебры логики является закон двойственности.
Пусть формула A содержит только операции конъюнкции, дизъюнкции иотрицания. Для операции конъюнкции двойственной считается дизъюнкция, адля дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х y) z двойственнойформулой будет (х y) z. Для двойственных формул справедлива следующаятеорема: если формулы A и B равносильны, то равносильны и двойственные имформулы, то есть A* = B*.
Данную теорему оставим без доказательства.С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведенияформул к заданному виду, упрощения формул.Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы , если α содержитменьше букв и логических операций. Например, для формулы ( (x y) x y) y можно записать следующую цепочку преобразований, приводящих ее к болеепростому виду:( (x y) x y) y = (x y x y) y = (x y) y = y.Функции алгебры логикиЗначение формулы алгебры логики полностью зависит от значений входящих в нее высказываний.
Поэтому такая формула может считаться функциейвходящих в нее элементарных высказываний. Например, (x y) z являетсяфункцией f(x, y, z). Естественно, значения этой функции и входящих в нее элементов могут принимать значения истина или ложь. Тождественно истинные илитождественно ложные функции представляют собой константы.Каждую функцию алгебры логики можно записать в виде формулы илипредставить таблицей истинности. Как уже было отмечено выше, таблица истинности для n переменных содержит 2n строк.
Следовательно, каждая функция алгебры логики принимает 2n значений, состоящих из 0 или 1. Общее же числоnнаборов значений, состоящих из 0 и 1, длины 2n равно 22 . В частности, числоразличных функций от одной переменной равно четырем.хf1(x)f2(x)f3(x)F4(x)0110011010Из этой таблицы следует, что две функции являются константами f1(x) = 1и – f2(x) = x, а остальные f3(x) = x и f4(x) = 0.Представление произвольной логической функции в виде формулы алгебры логикиПусть с помощью таблицы истинности задана произвольная функция алгебры логики n переменных F(x1, x2, …, xn). Рассмотрим формулу:F(1, 1, …, 1) x1 x2 … xn F(1, 1, …, 1, 0) x1 x2 … xn-1 xn (1) F(1, 1, …, 0, 1) x1 x2 … xn-1 xn F(0, 0, …, 0) x1 x2 … xnкоторая составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой первый член является значением функции F при некоторых определенных значениях ее переменных, остальные же члены конъюнкции представляют собой сами переменные или их отрицания.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
