Навигация
Практическое применение методов математической логики
34329
знаков
6
таблиц
25
изображений
1.2 Практическое применение методов математической логики
Всякая логическая функция «n» переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных (то есть всевозможных наборов двоичных векторов длины «n»), а в правой части приведены значения функции на этих наборах. При любом фиксированном упорядочении наборов значений переменных логическая функция «n» переменных полностью определена вектор-столбцом своих значений, то есть вектором длины 2n. Поэтому число различных логических функций «n» переменных будет 
. В самом деле, для одного набора значений своих переменных (строка левой части таблицы) значение функции может быть либо 1, либо 0 (две возможности). Число же возможных различных наборов аргументов функции, как уже отмечалось равно 2n, поэтому число различных логических функций будет/1/.
Заданием в данном пункте является построение таблицы истинности для следующего высказывания:
,
Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. “Истинность” или “ложность” предложения – это истинностное значение высказывания. Каждому высказыванию сопоставляется переменная, равная 1, если высказывание истинно, и равная 0, если оно ложно. Эти высказывания будут считаться простыми. Из простых высказываний с помощью логических связок могут быть построены составные высказывания. В таблице 1 приведены некоторые логические связки, используемые при задании данной функции (1).
Таблица 1-Логические связки
| Название | Обозначение |
| Конъюнкция | & |
| Импликация | ® |
| Сумма по модулю два | Å |
| Штрих Шеффера | | |
| Отрицание | Ø |
| Дизъюнкция | Ú |
| Стрелка Пирса | ¯ |
Правильно построенные составные высказывания называются (пропозиционарными) формулами. Истинностное значение формулы определяется через истинностные значения её составляющих в соответствии с единой таблицей истинности (таблица 2).
Таблица 2-Истиностные значения формул высказывания
| Х1 | Х2 | X1 &X2 | X1® X2 | X1 ÅX2 | X1Ú X2 | ØX1 | X1¯ X2 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Для того чтобы составить таблицу истинности для формулы, необходимо выполнить последовательность всех логических операций.
, (1)
После последовательного выполнения всех логических операций составляется таблица истинности для данной функции
Таблица 3- Таблица истинности функции (1)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| x | y | z | & |
|
|
|
|
|
|
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
Приведение функции к конъюнктивным и дизъюнктивным нормальным формам. Конъюнктивным (дизъюнктивным) одночленом от переменных а1, а2, а3,…,аn называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений (конъюнктивных одночленов), называется дизъюнктивной нормальной формой (ДНФ) данной формулы. Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений (дизъюнктивных одночленов), называется конъюнктивной нормальной формой (КНФ) данной формулы /2/. Справедливы следующие теоремы: любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде ДНФ по формуле:
V
(2)
Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде КНФ.
L
(3).
Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание /2/.
Искомая ДНФ для функции (1) имеет вид:
Искомая КНФ для функции (1) будет иметь следующий вид:
В расчетах ДНФ и КНФ использована методика /2/.
Построение полинома Жегалкина.
Представление булевой функции над базисом {0,1,v,Å} называется полиномом Жегалкина.
Таким образом, всякая булева функция представима в виде:
где ∑ - сложение по модулю два, знак · обозначает конъюнкцию/7/.
Для функции f(x,y,z)(1) полином Жегалкина имеет вид:
P(x, y, z)=b0×1Åb1×xÅb2×yÅb3×zÅb4×x×yÅb5×x×zÅb6y×zÅb7x×y×z
Метод неопределенных коэффициентов заключается в том, что путем последовательной подстановки переменных x, y, z и соответственно значений функции при этих переменных, из таблицы 1 в данный полином (4), строится система уравнений:
0=b0×1Åb1×0Åb2×0Åb3×0Åb4×0×0Åb5×0×0Åb60×0Åb70×0×0
0=b0×1Åb1×0Åb2×0Åb3×1Åb4×0×0Åb5×0×1Åb60×1Åb70×0×1
1=b0×1Åb1×0Åb2×1Åb3×0Åb4×0×1Åb5×0×0Åb61×0Åb70×1×0
0=b0×1Åb1×0Åb2×1Åb3×1Åb4×0×1Åb5×0×1Åb61×1Åb70×1×1
0=b0×1Åb1×1Åb2×0Åb3×0Åb4×1×0Åb5×1×0Åb60×0Åb71×0×0
0=b0×1Åb1×1Åb2×0Åb3×1Åb4×1×0Åb5×1×1Åb60×1Åb71×0×1
0=b0×1Åb1×1Åb2×1Åb3×0Åb4×1×1Åb5×1×0Åb61×0Åb71×1×0
0=b0×1Åb1×1Åb2×1Åb3×1Åb4×1×1Åb5×1×1Åb61×1Åb71×1×1
По свойству суммы по модулю два находится b:
b0=0, b1=0, b2=1, b3=0, b4=1, b5=0, b6=1, b7=1
Полином Жегалкина будет иметь вид:
¦(x, y, z) = y Å x×y Å y×z Å x×y×z
Правильность построения полинома проверяется таблицей истинности:
Таблица 4 - Таблица истинности для полинома Жегалкина
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| x | y | z | x&y | Å | y&z | Å | x&y&z | Å |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Дифференцирование функции нескольких переменных.
Производной булевой функции ¦(xn) по совокупности
переменных 
называется функция:
На основе данной формулы (5) находится производная по одной переменной x
Для данной функции (1) производная по формуле (6) принимает вид:
Таблица 5 - Производная ∂¦⁄∂x для формулы(7)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| x | y | z |
| & |
|
|
|
|
|
|
|
|
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
Вектор значений функции (7) имеет вид:
Производная по двум переменным находится также по формуле (5):
Для данной функции (1) производная принимает вид:
Таблица 6 - Производная ∂2¦⁄∂(x;y) для формулы(9)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| x |
|
| & |
|
|
|
|
|
|
|
|
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
Вектор значений функции (6) имеет вид:
Похожие работы
... и др. Они сформировались путем интеграции экспертных и формализованных методов. Схема классификации методов приведена на рис. 1 Рис. 1 - Классификация методов исследования систем управления 2. МЕТОДЫ ФОРМАЛИЗОВАННОГО ПРЕДСТАВЛЕНИЯ СИСТЕМ В ИССЛЕДОВАНИЯХ В настоящее время известны различные классификации методов формализованного представления систем. В результате этого методы, иногда ...
... . Вторая группа - методы формализованного представления систем управления, основанные на использовании математических, экономико-математических методов и моделей исследования систем управления. Среди них можно выделить следующие классы: аналитические (включают методы классической математики - интегральное исчисление, дифференциальное исчисление, методы поиска экстремумов функций, вариационное ...
... на одном этапе исследования, а иные – на другом. ЗАКЛЮЧЕНИЕ В процессе написания курсовой работы мною была изучена такая тема: «Аудит как метод исследования». Выяснила, что аудит входит в комплексно-комбинированные методы исследования систем управления, это указано на рис. 1, см. приложение 1. Комплексно-комбинированные методы исследования систем управления базируются на использовании ...
... . Это обстоятельство учитывается не только на этапе построения модели, но и на завершающей стадии, когда происходит объединение и обобщение результатов исследования, получаемых на основе многообразных средств познания. Моделирование - циклический процесс. Это означает, что за первым четырехэтапным циклом может последовать второй, третий и т.д. При этом знания об исследуемом объекте расширяются и ...
0 комментариев