Главная страница 1
скачать файл


Элементы логики

Основные понятия формальной логики

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

Сам термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон».

Логика использует ряд основных понятий и описывает действия над ними, подчиняющиеся законам логики. К этим основным понятиям логики относятся следующие.



Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или ложно. Заметим. Что любое высказывание не может быть одновременно истинным и ложным, а принимает только одно из этих двух возможных логических значений: ИСТИНА или ЛОЖЬ. Эти значения называются логическими постоянными, или логическими константами.

Утверждение – суждение, которое требуется доказать или опровергнуть, например, сумма внутренних углов треугольника равна 180.

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

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

Область знаний, которая изучает истинность или ложность высказываний называется математической логикой. Утверждения в математической логике называются логическими выражениями.

Логическое выражение представляет собой запись или устное утверждение, в которое наряду с постоянным, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая единица_ или ЛОЖЬ (логический ноль).

Подобно тому, как для описания действий над переменными величинами был разработан раздел математики – алгебра, так и для обработки логических выражений в математической логике была создана алгебра высказываний или алгебра логики.

Поскольку основы такой алгебры были заложены в трудах ирландского Джорджа Буля (середина  века), то алгебра логики получила также название булевой алгебры. Таким образом математический аппарат булевой алгебры позволил формализовать действия над логическими выражениями и явился базой для разработки логических элементов и в, целом логических основ для построения компьютера.

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



Логическая операция КОНЪЮНКЦИЯ определяет соединение двух логических выражений с помощью союза И. Эта операция называется логическим умножением и обозначается символами  или .


А

В

А  В

1

1

1

1

0

0

0

1

0

0

0

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

Таким образом, таблица истинности имеет следующий вид:

В качестве примера можно рассмотреть такую схему:

С
читаем истинным высказывание «Выключатель замкнут» и высказывание «Лампочка горит». Высказывание «лампочка горит будет истинным в том и только в том случае, когда выключатель А и выключатель В будут замкнуты одновременно.



Логическая операция ДИЗЪЮНКЦИЯ определяет соединение двух логических выражений с помощью союза ИЛИ. Эта операция называется логическим сложением и обозначается значком .


А

В

А  В

1

1

1

1

0

1

0

1

1

0

0

0
Сложное высказывание “А или В” истинно тогда и только тогда, когда истинно хотя бы одно из высказываний А, В, и ложно лишь в одном случае – когда оба эти высказывания ложны.

Таблица истинности дизъюнкции имеет следующий вид:

В качестве примера рассмотрим схему:

Лампочка будет гореть, когда замкнут хотя бы один из выключателей А или В..




А

В

1

0

0

1
Л
огическая операция
ОТРИЦАНИЕ или ИНВЕРСИЯ определяется над одним аргументом (простым или сложным выражением) следующим образом: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот, если исходное выражение ложно, то его отрицание буде истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. Операция отрицания обозначается чертой сверху, а ее результат определяется следующей таблицей.
ПОНЯТИЕ О ПРИНЦИПЕ ДЕЙСТВИЯ АРИФМЕТИКО-ЛОГИЧЕСКОГО УСТРОЙСТВА ЭВМ

При изучении различных устройств компьютера приходится рассматривать такие его логические элементы, в которых реализуются сложные логические выражения. Логический элемент – это электронное устройство, реализующее одну из логических функций. Здесь мы не будем рассматривать физические основы этих электронных устройств, реализую­щих основные логические операции. Для нас важно другое: эти электронные устройства, получая значения истинности отдельных простых высказываний (в виде, например, электрических сигналов: 1 – наличие сигнала, 0 – отсутствие сигнала), могут выдавать значения истинности конъюнкции, дизъюнкции, отрицания., Эти электронные устройства называют функциональными элементами. Для понимания дальнейшего нам достаточно ознакомиться с крат­кими характеристиками этих элементов.

Элемент НЕ реализует отрицание; он имеет один вход и один выход. Если на вход подается сигнал, то на выходе сигнал всегда отсутствует; если на входе сигнала нет, то на выходе сигнал есть.

Элемент И реализует конъюнкцию; он имеет два или более входов и один выход. На выходе сигнал появляется тогда и только тогда, когда на все входы поданы сигналы

Элемент ИЛИ реализует дизъюнкцию; он имеет два или более входов и один выход. На выходе сигнал появляется тогда и только тогда, когда хотя бы на один вход его подан сигнал

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

Пример 1. Составим функциональную схему, реализующую такую логическую формулу:

f(x1,x2)=(x1+x2)*x1

Функциональная схема будет иметь два входа на которые будут подаваться сигналы, соответствующие значениям x1 и x2. На этой схеме будет один выход, на котором будет появляться сигнал, соответствующий значению данной логической функции при данных значениях x1 и x2.

В функциональной схеме будет столько элементов, сколько операций в самой формуле. В логической формуле три операции: отрицание, дизъюнкция, конъюнкция. Значит в функциональной схеме три элемента: элемент НЕ (он преобразует сигнал в x1), элемент или (он, получив на входы два сигнала x1 и x2, на выходе выдаст сигнал, соответствующий значению дизъюнкции x1+x2), элемент И (на два входа этого элемента подаются сигналы (x1+x2) и x1, на выходе выдается сигнал, соответствующий значению f(x1,x2). Построенная таким образом схема имеет вид:

Решение задач базируется на умении строить таблицы истинности для логических (булевских) уравнений.

Сначала нужно спланировать число строк и столбцов такой таблицы. При определении числа строк необходимо некоторым регулярным образом перебрать все возможные сочетания логических значений 0 и 1 исходных выражений x1 и x2, из которых формируется заданное сложное логическое выражение.

Столбцы таблицы истинности соответствуют значениям исходных выражений x1 и x2, промежуточных результатов, а также искомого окончательного результата – значения сложного арифметического выражения (x1+x2)*x1

Построим таблицу истинности для заданного логического выражения:


x1

x2

x1

x1+x2

(x1+x2)*x1

0

0

1

1

0

0

1

1

1

0

1

0

0

0

0

1

1

0

1

1

Пример 2. Решить булевское уравнение.

(x1+x3)*(x2+x4)=x3



Решение: Построим таблицу истинности для левой части


x1

x2

x3

x4

x3

F1=x1+x3

x4

F2=x2+x4

F1*F2

F1*F2

0

0

0

0

1

1

1

1

1

0

0

0

0

1

1

1

0

0

0

1

0

0

1

0

0

0

1

0

0

1

0

0

1

1

0

0

0

0

0

1

0

1

0

0

1

1

1

1

1

0

0

1

0

1

1

1

0

1

1

0

0

1

1

0

0

0

1

1

0

1

0

1

1

1

0

0

0

1

0

1

1

0

0

0

1

1

1

1

1

0

1

0

0

1

1

1

0

0

0

1

1

0

1

0

0

1

1

1

1

0

1

0

1

1

0

1

0

0

0

1

1

1

0

0

1

1

1

1

1

0

1

1

0

1

1

1

0

1

1

0

1

1

1

0

0

1

1

1

1

0

1

1

1

1

0

1

0

1

1

0
Построим совмещенную таблицу истинности для левой и правой частей уравнения и знаком + пометим строки с совпадающими значениями выражений


x1

x2

x3

x4


(x1+x3)*(x2+x4)

x3




0

0

0

0

0

0

+

0

0

0

1

1

0




0

0

1

0

1

1

+

0

0

1

1

1

1

+

0

1

0

0

0

0

+

0

1

0

1

0

0

+

0

1

1

0

1

1

+

0

1

1

1

1

1

+

1

0

0

0

0

0

+

1

0

0

1

1

0




1

0

1

0

0

1




1

0

1

1

1

1

+

1

1

0

0

0

0

+

1

1

0

1

0

0

+

1

1

1

0

0

1




1

1

1

1

0

1



Сочетание значений переменных в помеченных строках являются решениями уравнения, т.е. ответом является таблица вида:



x1

x2

x3

x4

0

0

0

0

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

0

1

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



Регистр представляет собой электронный узел, предназначенный для хранения многоразрядного двоичного числового кода. Такой код может быть числовым кодом команды, выполняемой процессором, либо кодом некоторого числа (данного), которое используется при выполнении данной команды. Упрощенно можно представить регистр как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа.

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



Сумматор – это электронная схема, предназначенная для выполнения операции суммирования двоичных числовых кодов. При суммировании по правилам двоичной арифметики двух единиц результат равен 10 и происходит перенос в старший двоичный разряд. Для реализации простейшей операции суммирования одноразрядных двоичных чисел используется логическая схема (одноразрядный сумматор), составленная из следующих логических элементов: двух элементов И, одного элемента ИЛИ и одного элемента НЕ. Эта схема имеет три входа (два слагаемых и возможный перенос из предыдущего разряда) и два выхода (сумма и возможный перенос в следующий разряд). Многоразрядный сумматор строится как логическая схема на основе одноразрядных двоичных сумматоров.

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



Смотрите также:
Умение правильно рассуждать необходимо в любой области человеческой деятельности. Логика, как наука о том какие формы рассуждений правильны возникла немногим более двух тысяч лет тому назад
214.77kb.
Для успешного изучения геометрии важно иметь хорошее воображение. Правда воображение и внимание, умение правильно оценить увиденное полезно при изучении любого предмета и в любой профессии
25.36kb.
"Изменение глаголов по временам" для 3 класса
48.83kb.
В международный стандарт классификации профессий в 1988 году было занесено 9333 профессии, а в нашей стране специалисты насчитали 7000 профессий. По данным социологов, о чём в своё время написал М. Х
128.97kb.
[об образовании гор и минералов] (Фрагменты из «Книги исцеления»)
162.35kb.
Мне пришлось работать рядом более 30 лет. Дело еще и в том, что М. Г
51.76kb.
Эпоха великих географических открытий
136.28kb.
1. Специальная часть 2
1097.48kb.
Классный час по теме: "Что означают наши имена" Цели: 1 Познакомить учащихся со значением их имен
72.69kb.
Бременские музыканты
45.59kb.
Анализ нравственного конфликта
130.67kb.
Универсальная геометрия в природе и архитектуре
608.26kb.