Дизъюнктивные и конъюнктивные нормальные формы

Поэтому возможности схемы можно выявить, изучая соответствующую ей формулу, а упрощение схемы можно свести к упрощению формулы.Пример 3.1. Составить РКС для формулы (x̅˄y) →(zvx) .Решение. Упростим данную формулу с помощью равносильных преобразований:x̅ ˄ y) →(zvx) = vzvx = x vy̅vz vx=x vy̅vz .Тогда РКС для данной формулы имеет вид:3.2. Решение логических задач с помощью алгебры логики.Условие логической задачи с помощью соответствующих обозначений записывают в виде формулы алгебры логики. После равносильных преобразований формулы получают ответ на все вопросы задачи.Пример 3.2. После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:а)если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;б)если поедут Арбузов и Вишневский, то поедет и Брюквин.Требуется:1)ввести краткие обозначения для сформулированных условий и составить логическую формулу, выражающую принятое решение в символической форме;2)для полученной формулы найти возможно более простую равносильную формулу;3)пользуясь найденной более простой формулой, дать новую и более простую словесную формулировку принятого решения о составе участников экспедиции.Решение. Назначение в экспедицию Арбузова, Брюквина и Вишневского обозначим буквами А, Б, В соответственно. Тогда условие а) можно записать в виде А → Б v В, а условие б) в виде А& В → Б. Так как оба условия должны выполняться одновременно, то они должны быть соединены логической связкой «и». Поэтому принятое решение можно записать в виде следующей символической формулы:(А → Б v В)&(А&В → Б).2. (А → Б v В)&(А&В → Б)= (A̅vБ vB)&(A̅ vB̅vБ) == (A̅vБ)v(B&B̅) =А→Б.3. Символическую формулу читаем так: «Если поедет Арбузов, то поедет и Брюквин». Это и есть наиболее простая словесная формулировка принятого решения о составе экспедиции.ЗаключениеВ отличие от случаев логики высказываний и элементарной геометрии, для логики первого порядка не существует общей процедуры принятия решения. С другой стороны, учитывая соответствующие аксиомы в качестве предпосылок, все математические рассуждения могут быть выражены в логике первого порядка, и именно поэтому так много внимания было уделено процедурам доказательства для этой области.Список использованной литературыВиноградова М.С., Ткачев С.Б. Булевы функции. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. — 32 с.Математическая логика. — Пермь: Изд-во ПГТУ, 1998. — 17 с.Поздняков С.Н., Рыбин С.В. Дискретная математика.2010. — С. 303.Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с. - (Высшее образование)P.L. Hammer, I.G. Rosenberg, S. Rudeanu, On the minimization of pseudo-Boolean functions, Stud. Cerc. Mat. 14 (1963) 359–364.P.L. Hammer, S. Rudeanu, Boolean Methods in Operations Research and Related Areas, Springer, Berlin, 1968.Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи: Пер. с англ.- М.: Мир, 1982.Лупанов О.Б., Об одном подходе к синтезу управляющих систем — принципе локального кодирования, Проблемыкибернетики, вып. 14, М., Наука, 1965, С. 31-110.Сидельников В.М., Криптография и теория кодирования, Московский университет и развитие криптографии в России. Материалыконференции в МГУ 17-18 октября 2002 г. - М.: МЦНМО, 2003, С. 49–84.Яблонский С. В., Введение в дискретную математику, М.: Наука, 1979.[5] Яблонский С. В., О невозможности элиминации перебора при решении некоторых задач теории схем, ДАН СССР, 1959, т. 124, N 1, С. 44-47.Alon N., Spencer J., The Probabilistic Method, Wiley, 1992.Andreev A., Clementi A., Rolim J., Optimal Bounds for the Approximation of Boolean Functions and Some Applications, ECCC, TR95-041, 1995.Cook S., The complexity of theorem proving procedures, Proc. Third Annual ACM Symp. on Theory of Computing, Association for Computing Machinery, New York, 1971, pp. 151-158.Goldreich O., Introduction to Complexity Theory, Lecture Notes for a Two-Semester course [1999], http://www.wisdom.weizmann.ac.il/mathusers/oded/cc99.htmlKabanets V., Cai J., Circuit Minimization Problem, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 73-79, 2000.Razborov A., Rudich S., Natural Proofs, Journal of Computer and System Sciences, 49:149-167, 1994.