Автоматизация решения некоторых задач в алгебре.

Автоматизация решения некоторых задач Булевой Алгебры.Выполнила: Солдатова Людмила Станиславовна
Содержание
ВведениеАлгебра БуляСоставление таблиц истинности для ф-ций алгебры Буля. Автоматизация процесса.Приложение AВсевозможные значения ф-ции n-переменных и СДНФ. Автоматизация процесса.Приложение B
Введение
Постиндустриальное общество, в котором мы живем, постепенно преобразуется в информационное. Напомню, что информационное общество – это историческая фаза развития цивилизации, в которой главными продуктами производства становятся информация и знания. Огромное место в нашей жизни теперь занимает скорость получения и обработки информации. Чрезвычайно важна ее актуальность. И на фоне всего сказанного очень контрастирует тот факт, что решение многих задач в обучении студенты вынуждены реализовывать «на листочке». Хотя задачи являются алгоритмическими, легко программируемыми, быстро решаемыми на современных ПК. На мой взгляд обучаемый должен понять только принцип решения, а не тратить часы на «писанину». Именно поэтому я разработал несколько простых программок, решающих ряд задач из курса математической логики. Им и посвящен мой доклад. Итак, начнем!
Алгебра Буля
Алгеброй Буля называется непустое множество A с двумя бинарными операциями (конъюнкция, И), (дизъюнкция, ИЛИ), унарной операцией (инверсия, НЕ) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы: ассоциативностькоммутативностьзаконы поглощениядистрибутивностьдополнительность
Составление таблиц истинности для ф-ций алгебры Буля. Автоматизация процесса.
Функцией алгебры логики n-переменных (или функцией Буля) называется функция n переменных, где каждая переменная принимает два значения: 0 и 1, и при этом функция может принимать только одно из двух значений: 0 или 1. Проще говоря, функция – это правило, по которому входному набору значений ставится в соответствие 0 или 1. Каждый элемент этого входного набора может принимать только значение истины или лжи. Приведу маленький пример. Ниже приведена ф-ция 2 переменных:¬(a V b) ≡ f(a, b)Это отрицание дизъюнкции. Различных комбинаций a и b может быть 4 штуки. Составим таблицу истинности для этой функции:
a
b
f(a, b)
0
0
1
0
1
0
1
0
0
1
1
0
Легко, не правда ли? Даже человек, который первый раз видит материал, составит таблицу за минуту, как максимум.А если переменных будет не 2, а 5, 10, 19? Или функция будет сложнее? Сколько времени потребуется тогда? А если человек запутается, сделает вычислительную ошибку (от которой на 100% застрахована ЭВМ)? Тогда вычисление значения ф-ции будет, как минимум, сильно затруднено. Я думаю, что мы подошли к главному. Как раз для тех случаев, где возможно исключить рутинные расчеты, я составила простенькую программу на языке JavaScript, которая возьмет роль счетовода на себя. И будет делать это в миллионы раз быстрее (и точнее), чем человек.
Думаю, что многие спросят, почему языком реализации я выбрала именно JavaScript? Для данной задачи он имеет довольно большое количество плюсов, при относительно малом количестве минусов. Как его достоинства (для решения данной задачи) можно отметить:Кроссплатформеность и кроссбраузерность. JavaScript будет выполнятся на подавляющем большинстве компьютеров и ОС.Возможность генерации кода в run-time для последующей передачи его на исполнение. Это возможно, потому что язык JavaScript является интерпретируемым, а не компилируемым.Поддержка работы с регулярными выражениями. Возможность простой реализации таблиц. Т.к. JavaScript является языком Web-разработчиков, то он может управлять HTML-контентом страницы. А таблицы в HTML делаются очень просто.
Ниже представлен скриншот программы, рассчитавшей таблицу значений для отрицания дизъюнкции (ф-ции, приведенной в примере выше):Т.е. от пользователя требуется только ввести количество переменных и функцию. Остальное сделает программа. Программа может работать абсолютно с любым количеством переменных (n, где n принадлежит N). Ее возможности ограничены только возможностями компьютера, где она запущена.
Приложение A
Я специально не стала перегружать свой рассказ техническими подробностями о конкретных моментах реализации программы, ведь это секция математики! Но я не исключаю, что кого-нибудь заинтересует именно аспект технической реализации. Поэтому здесь, в приложении А, я привела исходный текст программы:Приложение A.
Всевозможные значения ф-ции n-переменных и СДНФ. Автоматизация процесса.
Чуть выше мы рассмотрели само понятие булевой ф-ции от n переменных. А сколько всего может быть функций n-переменных? Оче- видно, что каждую функцию алгебры логики можно задать с помощью таблицы истинности, которая будет содержать 2n строк. Таким образом, ф-ция n переменных полностью определяется набором значений из нулей и единиц длины 2n . Общее же число наборов, состоящих из нулей и единиц, длины 2n равно 22n. Значит, число различных функций алгебры логики n переменных равно 22n. Вторая моя программа как раз и составляет по известному n всевозможные значения функций. Как вы понимаете, для человека этот процесс будет очень трудоемок. Но было бы неплохо иметь не только таблицу значений всевозможных ф-ций, но и их формулы. Тут мы плавно подходим к такому понятию, как СДНФ.Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.
Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются четыре свойства совершенства . Такая ДНФ А называется совершенной дизъюнктивной нормальной формой формулы А (СДНФ А ). СДНФ можно получать из таблицы истинности.Я понимаю, что сухой текст несколько сложен для восприятия, поэтому я проиллюстрирую его простым примером. Предположим, что есть F(X1, X2, X3) . Известна ее таблица истинности:
x1
x2
x3
F(x1,x2, x3)
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
1
Для наборов значений переменных (1,1,0), (1,0,1), (0,1,0), (0,0,0), на которых функция принимает значение 1, запишем конъюнкции Х1Х2¬Хз , Х1¬Х2Хз, ¬Х1Х2¬Хз, ¬Х1¬Х2¬Хз , а искомая формула, свойствами совершенства, имеет вид: Х1Х2¬Хз V Х1¬Х2Хз V ¬Х1Х2¬Хз V ¬Х1¬Х2¬Хз.Моя программа как раз и ищет СДНФ для каждой сгенерированной ф-ции. Чтобы не быть голословным, приведу скриншот работы программы для ф-ции 1 переменной:
По техническим принципам работы она весьма сильно напоминает предыдущую программу, поэтому я не буду их перечислять. В приложении B можно найти исходный текст программы.
Приложение B
Я несколько раз упомянула о правилах совершенства. Однако в моем докладе ранее о них не говорится. Я приведу их здесь:1) Каждое логическое слагаемое формулы содержит Все переменные, входящие в функцию F(X1, X2, ...., Xn ). 2) Все логические слагаемые формулы различны. 3) Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание. 4) Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.Исходный текст программы вы можете найти здесь.