Некоторые, из приведенных в таблице функций уже рассматривались ранее. Так например, функции F₀ и F₁₅ являются тождественно постоянными - F₀(A,B) = 0, F_l5(A,B)- 1 (логическими константами). F₁(A.B)=AB - являет­ся конъюнкцией логических переменных А и В, F₇(A,B) = А + В - дизъюнкци­ей, F₉(A, B) = А В - эквиваленцией, a F₁₃(A,B) = А В импликацией. Функции F_12, F_l0, F₆, F₃ и F₁₄ являются, соответственно, отрицанием А, от­рицанием В исключающей дизъюнкцией А и В, стрелкой Пирса и штрихом Шеффера.

Совокупность фиксированных значений истинности и аргументов A₁,A₂,A₃,....An принято обозначать в виде последовательности нулей и единиц.

например 001 …110. Такие последовательности нулей и единиц называют наборами и говорят: что функция F(A^*₁,A^*₂,A^*₃,....A^*n) рассматривается на кон­кретном наборе (A^*₁,A^*₂,A^*₃,....A^*n), где А*_n есть либо ноль либо единица, а индекс указывает на то, что из всевозможных наборов рассматривается n- ая комбинация.

По своему виду конкретные наборы соответствуют n-разрядной записи числа в двоичной системе счисления. Поэтому конкретные наборы часто пред­ставляют в виде двоичных или десятичных их числовых эквивалентов. Воз­можным наборам значений для некоторой логической функции от двух логических переменных А и В соответствуют четыре двоичных числа - 00, 01, 10 и 11 или их десятичных эквиваленты - 0, 1, 2 и 3. Для функции от трех логиче­ских переменных соответствуют восемь двоичных чисел - 000, 001, 010 011, 100, 101, 110, 111 или десятичных числа - 0, 1, 2 , 3. 4, 5, 6 и 7. Дли введен­ных логических функций от F₀ до F₃, представленных в первой таблице, и от F₀ до F₁₅, представленных во второй таблице, их десятичный индекс соответствует десятичному эквиваленту распределения их двоичных значений, если их запи­сать в виде двоичных чисел сверху вниз.
Пример 1

Какие из приведенных ниже выражений являются формулами логики высказываний, а какие нет?

1. 2. 3. ; 4.

---

Решение.

Здесь выражения под номерами 1, 2 не являются формулами логики высказываний (в 1 - нельзя записать подряд две логические операции, в 2 - высказывание не может начинаться с символа логического сложения). Формулами логики высказываний является формулы под номерами 3 и 4.

Иногда вводят в рассмотрение понятие "подформулы". Если F- формула, а - какая-либо ее связная часть, которая сама является формулой, то на­зывается подформулой формулы F. Понятие подформулы не следует путать с понятием связной части формулы. Связная часть формулы - это часть форму­лы, которая выписана из нее без пропусков. Например, в формуле есть следующие подформулы А, В, С, АВ, , . Никаких других подформул данная формула не имеет. Выражение является частью формулы, но подформулой не является. так­же не является подформулой, поскольку не является се связной частью. Глав­ной подформулой формулы Fназывается такая ее подформула, которая не явля­ется частью никакой другой подформулы формулы F. Например, формула имеет две главные подформулы (А + В) и .

Логические формулы допускают различные тождественные преобразова­ния с целью их упрощения или придания им более удобного для применения вида. Запись формулы часто можно упростить:

1) Внешние скобки можно опустить;

2) Если подформула имеет вид , то скобки можно опустить. Та­ким образом, правила опускания скобок аналогичны соответствующим прави­лам опускания скобок в арифметике и алгебре, нужно лишь учитывать при­оритетность выполнения логических операции.

Пример 2. Опустить лишние скобки в формуле



Пример 3. Восстановите опушенные скобки в формуле

---

Для каждой формулы алгебры логики может быть построена соответст­вующая таблица истинности. Задача построения таблицы истинности для формулы, состоящей из n переменных, есть задача построения двоичной функции (Булевой функции), соответствующей данной формуле.

Алгоритм построения таблиц истинности

Пусть задана логическая формула, и нам надо построить ее таблицу ис­тинности. Для построения таблицы истинности этой формулы необходимо выполнить следующие действия:

• 
  Определить количество переменных, входящих в формулу и составить табли­цу всевозможных значений переменных (наборов, иногда также говорят - оценок переменных), от которых зависит данная формула. Конкретные наборы можно рассматривать как числа в двоичной системе счисления и их удобно располагать в порядке возрастании от 0 до 2ⁿ -1, если количество переменных равно n.
  
• 
  Провести анализ построения этой формулы с учетом расположения скобок и приоритетности порядка выполнения логических операций. Выписать саму форму­лу, затем ее главные подформулы, затем под каждой подформулой снова выпишем главные подформулы и т.д. Количество столбцов в таблице должно быть равно сумме количества простых переменных и выделенных подформул плюс один стол­бец отводится на саму формулу. Общее количество строк должно быть на едини­цу больше, то есть 2ⁿ +1. Одна строка добавляется для записи переменных, всех подформул и самой формулы.
  
• 
  Поэтапно сверху вниз строить таблицу истинности, двигаясь слева направо, для всех подформул (лучше по порядку их выполнения). В результате получим таб­лицу истинности для исходной формулы.
  

Пример

Построить таблицу истинности для логической функции .

Оценка	А	В
m1	0	0	1	0	1	0
m2	0	1	0	0	1	0
m3	1	0	1	1	0	1
m4	1	1	0	0	1	1

---

Отношения между формулами алгебры логики

Из полученной выше таблицы истинности видно, что истинностные значения формулы точно совпадают со значением логической пере­менной А. Они либо одновременно ложны, либо одновременно истинны. Та­кие формулы называются равносильными или эквивалентными. Равносильные формулы могут содержать различное количество логических переменных. Даже в рассмотренном примере, левая часть зависит от двух логических переменных - А и В, а правая часть только от одной логической переменной А. Важно, чтобы формулы, которые называются равносильными, имели одинаковые зна­чения при одинаковых наборах логических переменных по тем переменным, от которых они зависят. Для обозначения равносильности пользуются обычно знаком равенства: =А

Упрощение логических формул может также проводиться но правилу подстановки. Если в формуле есть какая-либо подформула, которая равно­сильна другой формуле, то эту подформулу можно заменить равносильной. Для такой подстановки используются таблицы истинности, а на практике наи­более часто применяются законы математической логики.

С помощью таблиц истинности для формул, имеющих небольшое коли­чество переменных и число логических операций, можно достаточно просто проверить равносильность формул.

Пример

Проверить равносильность формул с помощью таблиц истинности:

1.

2.

3.

4.

5.

6.

А	В					А	В
0	0	1	1	1		0	0	1	1	1	1
0	1	1	1	1		0	1	1	0	1	1
1	0	0	0	0		1	0	0	1	0	0
1	1	1	0	1		1	1	0	0	0	1

---

А	В	А+В			А	В	АВ	А+АВ
0	0	0	0		0	0	0	0
0	1	1	0		0	1	0	0
1	0	1	1		1	0	0	1
1	1	1	1		1	1	1	1

А	В	АВ						А	В	А+В
0	0	0	1	1	1	1		0	0	0	1	1	1	1
0	1	0	1	1	0	1		0	1	1	0	1	0	0
1	0	0	1	0	1	1		1	0	1	0	0	1	0
1	1	1	0	0	0	0		1	1	1	0	0	0	0

---

Смотрите также файлы

• Программа по учебному курсу Химия Класс 8 Программу составила Киревичева Н. В 20202012 уч г 8 класс.doc

• Коммерциялы емес ашы акционерлік оам марбек дукеев атындаЫ.docx

• Контрольная работа по дисциплине Введение в профессиональную деятельность.docx

• П. А. Сивкова подпись, дата И. О. Фамилия.docx

• Самостоятельная работа по теме Цель занятия приобретение и закрепление знаний оюридической ответственности предприятий, загрязняющих окружающую среду, формирование умения применять их.docx