Элементарные логические функции

Стр 1 из 3Следующая ⇒

Тема 3. ЛОГИЧЕСКИЕ ОСНОВЫ ФУНКЦИОНИРОВАНИЯ ЭВМ

1. Логика высказываний. Основные понятия.

2. Элементарные логические функции.

3. Законы алгебры логики.

4. Способы представления логических функций.

5. Схемная реализация элементарных логических операций. Типовые логические узлы.

6. Решение логических задач.

Логика высказываний. Основные понятия

1. Логика - это наука о законах и формах мышления. Она изучает абстрактное мышление как средство познания объективного мира.

ГЛАВНАЯ ЗАДАЧА ЛОГИКИ состоит в том, чтобы ВЫЯВИТЬ, какие способы рассуждения правильные, а какие нет. Логика, как и теория алгоритмов - является теоретической основой современных ЭВМ и программирования. Слово логика в широком смысле означает науку о правилах рассуждений, а в узком смысле - совокупность правил, которым подчиняется процесс мышления.

В середине Х1Х века возникла и начала интенсивно развиваться математическая логика, применяющая для анализа рассуждений математические средства и методы. Именно она заложила теоретические основы последующей разработки языков программирования.

Основоположником математической логики является великий немецкий математик Готфрид Вильгельм Лейбниц. Он сделал попытку построить универсальный язык, с помощью которого споры между людьми можно было бы разрешать посредством вычислений, и привел соответствующие правила.

Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода. Математическая логика - это раздел математики, изучающий:

- Булеву алгебру;

- Алгебру отношений;

- Теорию доказательств.

Одним из основных разделов математической логики является алгебра логики (исчисление высказываний), основоположником которой был

Джордж Буль, положивший в основу своего логического учения методы алгебры (алгебра Буля). Алгебра логики в отличие от обычной алгебры оперирует не числами, а высказываниями.

Высказывание (суждение) - это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет. Таким образом, по своей сути высказывания фактически являются двоичными объектами и поэтому часто истинному значению высказывания ставят в соответствие 1, а ложному - 0.

Высказывания бывают простыми и сложными.

Простым высказыванием называют повествовательное предложение, относительно которого имеет смысл говорить, истинно оно или ложно. Никакая его часть не является самостоятельным высказыванием. Например: «Сейчас идет дождь», «Валентность кислорода равна двум».

Сложные высказывания состоят из нескольких простых высказываний, соединённых логическими операциями. Например: «Если придет друг, то мы пойдем в кино».

Логическими значениями высказываний является «истина» и «ложь». Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным. Приведем примеры высказываний:

1) 3 >1;

2) Курск - столица России;

3) Волга впадает в Каспийское море.

Высказывания 1 и 3 являются истинными. Высказывание 2 - ложным.

Следующие предложения высказываниями не являются:

1) Давай пойдем гулять;

2) 2*x>8;

3) a*x2+b*x+c=0;

4) Который час?

5) Будь внимателен!

6) Успеешь ли ты вовремя?

Подчеркнем еще раз, что отличительным признаком высказывания является свойство быть истинным или ложным, последние предложения этим свойством не обладают. Невозможно отнести неравенство 2 или уравнение 3 к высказываниям пока не определено значение Х. При x=3 высказывание «2*3>8» ложно, а при x=5 «2*5>8» - истинно.

При записи тех или иных логических выражений используется специальный язык, который принят в математической логике. В алгебре логики простым высказываниям ставятся в соответствие логические переменные, обозначаемые прописными буквами латинского алфавита. Следуя Джорджу Булю, истинное (true) высказывание A обозначим так, A=1. В том случае, когда A - ложное (false) высказывание, будем писать: A=0.

Например,

А — шесть - число четное. А = 1

(ИСТИНА)

В — Лондон — столица Франции. В = 0

(ЛОЖЬ)

С — Всякий квадрат есть параллелограмм. С= 1

(ИСТИНА)

Из простых высказываний можно строить сложные, называемые составными высказывания, соединяя простыми логическими операциями.

2. Над простыми высказываниями определены следующие основные операции:

1) логическое отрицание (инверсия, дополнение) выражаемая словом “не”) производится над одним элементом. Обозначается горизонтальной чертой сверху над именем переменной: Читается как НЕ (в базах данных и языках программирования обозначается NOT). Результат отрицания всегда противоположен значению аргумента. Логическая операция НЕ является унарной, т.е. имеет всего один операнд. Например, если А - простое высказывание «Идет дождь», то отрицанием является высказывание «Неверно, что идет дождь» или «Дождь не идет»;

2) логическое умножение (логическое «и», конъюнкция) выражаемая связкой “и” - это составное высказывание истинное тогда и только тогда, когда истинны оба высказывания, входящие в него. Читается как И (в базах данных и языках программирования обозначается AND) и обозначается обычно знаками х или ^ или & (читается как амперсэнд) являющимся сокращенной записью английского слова AND. Например, рассмотрим высказывание «Для установки ОС «Windows'95» требуется процессор не ниже 80386 и не менее 4 Мбайт оперативной памяти». Из него следует, что установка будет успешной только при одновременном выполнении обоих условий: даже если у вас в машине Pentium, но мало ОЗУ (равно как и при 8 Мбайт ОЗУ процессор 80286), «Windows'95» работать откажется;

3) логическое сложение (логическое «или», дизъюнкция) выражаемая связкой “или” - это составное высказывание ложное тогда и только тогда, когда ложны оба высказывания, входящие в него. Читается как ИЛИ (в базах данных и языках программирования обозначается OR). Обозначается символами + или V или |. Например, действительно, когда девушка просит друга подарить ей на день рождения букет цветов или пригласить в ресторан, можно без опасений сделать и то, и другое одновременно (впрочем, на практике в таком случае можно ограничиться чем-то одним).

4) логическое следование или импликация, операция, выражаемая связками “если ..., то”, “из ... следует”, “... влечет ...”, обозначается символом или = и в программировании обозначают «IMP». Импликацией двух высказываний А и В называют высказывание, это составное высказывание ложное тогда и только тогда, когда из истинного высказывания следует ложное (А - истинно, а В - ложно). Высказывание А является условием или посылкой импликации, а В - заключением или следствием импликации;

5) эквивалентность (двойная импликация), это логическая операция, выражаемая связками тогда и только тогда..., когда; необходимо и достаточно; равносильно; в том и только том случае. Обозначается символами Эквивалентными называются два суждения, которые одновременно истинны или одновременно ложны. То есть, составное высказывание A ~ B истинно в том случае, когда значения операндов совпадают.

С помощью этих операций можно представить (аналитически выразить) любую сколь угодно сложную логическую функцию. Функция в алгебре логики - это алгебраическое выражение, содержащее элементы алгебры логики А, В, С ..., связанные между собой операциями, определенными в этой алгебре.

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

Истинность составных высказываний, образованных в результате выполнения каких-либо логических операций над простыми высказываниями, зависит только от истинности исходных высказываний. Чаще всего для установления значений сложных высказываний используют таблицы истинности.

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

Элементарные логические функции

Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы аргументов, а в правой - соответствующие им значения функции. Таблица истинности может рассматриваться в качестве одного из способов задания логической функции. Логическую функцию порой называют функцией алгебры логики (ФАЛ).

Логическое значение высказывания «не А» (инверсия) определяется таблицей истинности:

X	NOT
0	1
1	0

Логическое значение высказывания «А ^ В» (конъюнкция) определяется таблицей истинности:

X	Y	X AND Y
0	0	0
0	1	0
1	0	0
I	1	1

Логическое значение высказывания «А v В» (дизъюнкция) определяется таблицей истинности:

X	Y	X OR Y
0	0	0
0	1	1
1	0	1
1	1	1

Логическое значение высказывания «А В» (импликация)

определяется таблицей истинности:

А	В	А В
0	0	1
0	1	1

1	0	0
1	1	1

Логическое значение высказывания «А В» (эквивалентность),

определяется таблицей истинности:

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

Заметим, что таблицы истинности находят широкое применение для:

• вычисления истинности сложных высказываний;

• установления эквивалентности высказываний;

• определения тавтологий.

Два сложных высказывания называют эквивалентными, если совпадают их таблицы истинности.

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

Формулы, принимающие значение “ложно” при любых значениях истинности входящих в них переменных, называются тождественно ложными формулами или противоречиями (например, высказывание “Катя самая высокая девочка в классе, и в классе есть девочки выше Кати”).Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно.

Если две формулы А и В “одновременно”, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Формулы, принимающие значение “истина” при любых значениях истинности входящих в них переменных называются тождественно истинными формулами или тавтологиями. Например, формула , соответствующая высказыванию “Этот треугольник прямоугольный или косоугольный”. Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный.

Высказывания, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний, а определяется только их структурой, называются тождественными или тавтологиями. Различают тождественно-истинные и тождественно-ложные высказывания.

Операции И, ИЛИ, НЕ образуют полную систему логических операций, из которой можно построить сколь угодно сложное логическое выражение.

В вычислительной технике также часто используется операция исключающее ИЛИ (XOR), которая отличается от обыкновенного ИЛИ только при Х=1 и Y=l. Обозначается символом

Таблица 2 - Дополнительные логические операции

А	В	А XOR В (A B)	NOT (А AND В)
0	0	0	1
0	1	1	1
1	0	1	1
1	1	0	0

Как видно из табл. 2, операция XOR фактически сравнивает на совпадение два двоичных разряда. Высказывание "A B" истинно тогда, когда истинно А или B, но не оба одновременно.

Свойства операции "исключающее ИЛИ"

Хотя теоретически основными базовыми логическими операциями всегда называют именно И, ИЛИ, НЕ, на практике по технологическим причинам в качестве основного логического элемента используется элемент И-НЕ (последняя колонка в табл. 2).

Функция (И-НЕ): Y = X1|X2 = NOT(X1X2)

Можно проверить, что на базе элементов И-НЕ могут быть скомпонованы все базовые логические элементы (И, ИЛИ, НЕ), а значит и любые другие, более сложные.

Базируется алгебра логики на отношении эквивалентности и трех упомянутых операциях: дизъюнкции (логическое сложение, операция ИЛИ), конъюнкции (логическое умножение, операция И) и отрицания (инверсия, операция НЕ).

Отношение эквивалентности обозначается знаком =.

Функции в алгебре логики - это алгебраическое выражение, содержащее элементы алгебры логики: А, В, С ..., связанные между собой операциями, определенными в этой алгебре.

Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий.

Алгебра логики определяется следующей системой аксиом:

Если в аксиомах произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы данной пары получается другая. Это свойство называется принципом двойственности.

С помощью аксиом можно получить ряд тождеств:

Для приведения логических выражений к эквивалентным, но более простым в записи используют ряд логических законов. Законы логики отражают наиболее важные закономерности логического мышления. В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений.

3. Законы алгебры логики:

-закон тождества. Всякое высказывание тождественно самому себе:

А=А

- закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

А&А=0

-закон исключения третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:

-закон коммутативности (или переместительный). Закон коммутативности говорит о том, что порядок переменных при выполнении операций не влияет на результат этой операции:

логическое сложение - А v В = В v А;

логическое умножение - А ^ В = В ^ А;

-закон ассоциативности (или сочетательный). Закон ассоциативности говорит о том, что переменные можно группировать в любом порядке как для операции конъюнкции, так и для операции дизъюнкции

(А v В) v С = А v (В v С) = (А v С) v В = А v В v С;

(а ^ в) ^ С = А ^ (в ^ с) = А ^ В ^ С;

-закон дистрибутивности (или распределительный). В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:

Дата добавления: 2021-12-10; просмотров: 36; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!