Файл: Методические указания для проведения практических работ по профессиональному модулю Проектирование цифровых устройств.docx

Значит солнечной погоды не будет разве, что прекратится дождь».

4. Пусть заданы следующие три простейших высказывания:

В – Билл глуп,

D - Джон умен

S - Билл не выиграет соревнования.

Переведите на ес­тественный язык высказывания, записанные с помощью алгебры высказыва­ний

1. 2.

Формулы логики высказываний. Оценка формулы.

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

Формулы логики высказываний и понятие логической функции является ос­новными понятиями алгебры высказываний. Формулой языка алгебры логики называется выражение, составленное из высказывательных переменных, логи­ческих операций и скобок. Можно дать более точное и более абстрактное оп­ределение формулы логики высказываний:

1. Пропозиционная переменная (некоторое высказывание) А и логические константы - 1 и 0 является формулами алгебры высказываний.

2. Если А формула алгебры высказываний, то А являются также формулой.

3. 
   Если А и В являются формулы алгебры высказываний, то формулами ал­гебры высказывании являются и формулы
   
4. 
   Никаких других формул в логике высказывании нет.
   

Формулы алгебры высказываний, зависящие от некоторого количества логических переменных A1, A2 ,A3,...,An, принято символически обозначать, как и в обычной математике, в виде - F(A1, A2 ,A3,...,An). Каждая формула представляет собой логическую функциювходящих в неe некоторых логических переменных, каждая из которых может принимать только значение 0 или 1. Отметим, что количество различных фиксированных комбинаций, которые может принимать а переменных A₁, A₂ ,A₃,...,An, равно 2п.

В дальнейшем понятие формулы алгебры высказываний и двоичной ло­гической функции будем считать эквивалентными, хотя пало сказать, что формул алгебры высказываний составленных из п переменных бесчисленное множество, а число двоичных функций от п переменных конечно и равно 2 . С ростом п число бинарных логических функций резко растет. При п-1 возможно всего 4 функций, при п = 2 число функций равно 16, а при п = 3 и п = 4 уже, соответственно, 256 и 65356.

---

В качестве примера приведем логические функции для случаев одного и двух логических переменных, как наиболее часто встречающихся в практике работы с формулами алгебры логики.

Двоичные функции от одной логической переменной

A	F0(A)	F1(A)	F2(A)	F3(A)
0	0	0	1	1
1	0	1	0	1

Двоичные функции от двух логических переменных

A	B	F0	F1	F2	F3	F4	F5	F6	F7
0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1
A	B	F8	F9	F10	F11	F12	F13	F14	F15
0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

---

Некоторые, из приведенных в таблице функций уже рассматривались ранее. Так например, функции 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 переменных, есть задача построения двоичной функции (Булевой функции), соответствующей данной формуле.

---