Курсовая работа: Применение алгебры высказываний в информатике
4. < меньше
5. >= больше или равно
6. <= меньше или равно
Отношение « равно» истинно для двух символьных величин, если их длина одинакова и все соответствующие символы совпадают. (Следует учитывать, что пробел - это тоже символ).
Символьные величины можно сопоставлять и в отношениях <, >, <=, >=. Сравниваются между собой не сами символы, а их внутренние коды.
Функция в алгебре логики – это алгебраическое выражение, содержащее элементы алгебры логики a, b, c…, связанные между собой операциями, определёнными в этой алгебре.
Примеры логических функций:
(a,b,c) = a + a*b*c + a+c;
(a,b,c) = a*b + a*c + a*b*c.
Согласно теоремам разложения функций на составляющие любая функция может быть разложена на конституэнты “1” :
(2) (a) = (1)*a + (0)*a;
(a,b) = (1,b)*a + (0,b)*a = (1,1)*a*a + (1,0)*a*b + (0,1)*a*b + (0,0)*a*b ит.д.
Эти соотношения используются для синтеза логических функций и вычислительных схем.
Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…». Составное высказывание, образованное с помощью операции импликации, ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).
Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «… тогда и только тогда, когда…». Составное высказывание, образованное с помощью операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.
Логический синтез вычислительных схем.
Рассмотрим логический синтез (создание) вычислительных схем на примере одноразрядного двоичного сумматора, имеющего два входа ( “a” и “b”) и два выхода (“S” и “P”) и выполняющего операцию сложения в соответствии с заданной таблицей:
| a | b | (a,b) = S | (a,b) = P | |
| 0 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 1 | |
где (a,b) = S – значение цифры суммы в данном разряде;
(a,b) = P – цифра переноса в следующий (старший) разряд.
Согласносоотношению (2), можнозаписать:
S = (a,b) = 0*a*b + 1*a*b + 1*a*b + 0*a*b = a*b + a*b;
P = (a,b) = 1*a*b + 0*a*b + 0*a*b + 0*a*b = a*b.
Самой простой логической операцией является операция НЕ (по-другому отрицание, дополнение или инверсия; обозначают NOTX). Результат отрицания всегда противоположен значению аргумента. Операция Не является унарной, т.е. имеет всего один операнд. В отличии от неё операции И (AND) и ИЛИ (OR) являются бинарными, так как представляют собой результаты действий над двумя логическими величинами.
Логическое И называют конъюнкцией, или логическим умножением, а ИЛИ – дизъюнкцией, или логическим сложением.
Операция И имеет результат «истина» только в том случае, если оба её операнда истинны. Например, рассмотрим высказывание «Для установки ОС “Windows’95” требуется процессор не ниже 80386 и не менее 4 Мбайт оперативной памяти». Из него следует, что установка будет успешной только при одновременном выполнении обоих условий: даже если у вас в машине Pentium, но мало ОЗУ, «Windows’95» работать откажется.
Операция ИЛИ «менее привередлива» к исходным данным. Она даёт истину, если значение «истина» имеет хотя бы один из операндов. Разумеется, в случае, когда справедливы оба аргумента одновременно, результат по-прежнему истинный.
Приведённые ниже таблицы значений переменных для логических операций называются таблицами истинности. В них указываются всевозможные
комбинации логических переменных Xи Y, а также соответствующие им результаты операций.
Основные логические операции
| X | Y | X AND Y | X OR Y |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| X | NOT X |
| 0 | 1 |
| 1 | 0 |