Скачивание материала началось

Предлагаем Вам установить расширение «Инфоурок» для удобного поиска материалов:

ПЕРЕЙТИ К УСТАНОВКЕ

Новый курс повышения квалификации!

Цифровая грамотность педагога. Дистанционные технологии обучения

Разработан летом 2020 специально для учителей

Успеть записаться

-50% До конца лета

Каждую неделю мы делим 100 000 ₽ среди активных педагогов. Добавьте свои разработки в библиотеку “Инфоурок”
Добавить авторскую разработку
и получить бесплатное свидетельство о публикации в СМИ №ФС77-60625 от 20.01.2015
Инфоурок Информатика КонспектыТеоретический материал к теме «Основы логики» курса информатики

Теоретический материал к теме «Основы логики» курса информатики

библиотека
материалов






















ОСНОВЫ ЛОГИКИ
Методические указания
к темам курса информатики





















Пермь

2009


Содержание с с

1. Понятие о логике как о науке. Практическое приложение логики.

Логика – наука (комплекс наук) о формах и способах правильного мышления. Под формой мышления понимают способ связи частей мыслимого целого (умозаключения, рассуждения, доказательства). Слово “логика” различные словари, научные или богословские, производят от древнегреческих слов

закон, порядок, слово, понятие, рассуждение, разум, сын Божий и др.

давать отчёт.

В русском языке понятия «логика вещей» и «порядок вещей» - синонимы. Человек, владеющий логикой, может отличать правильные мысли (цепочки мыслей, рассуждения) от неправильных. Если вы правильно, логично рассуждаете, то производите на окружающих благоприятное впечатление. Если вы обнаружите ошибку в рассуждениях ваших собеседников, то сможете одержать верх в дискуссии, полемике, споре, и не дадите себя обмануть или убедить в чём-либо помимо вашей воли.

Оттачивая искусство одерживать верх в дискуссиях собеседников, в судебных тяжбах, логика за историю своего развития прошла несколько этапов (общая (традиционная, аристотелева), символическая (математическая) и т.д.). Наиболее интересным и выгодным приложением достижений математической логики к практическим нуждам людей стало создание счётно-решающих устройств, электронных вычислительных машин. Человек сумел познать наиболее общие, присущие всем людям законы мышления и смоделировать работу своего мозга, «вручив» частично функции вычислений и умозаключений сложным техническим неживым устройствам.

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

Логика должна была начаться с осознания человеком того, что есть внешний мир и есть его видимость, образ мира в голове человека. Видим ли мы то, что есть на самом деле? Ответ на этот вопрос довольно сложен, и от того, кáк человек на него отвечает, зависит то, к какой теории познания он обращается, если даже сам человек не ведает ни о каких теориях познания.

Если мы скажем, что “то, что мы видим, ощущаем, и есть внешний мир”, что «внешний мир именно такой, каким мы его воспринимаем», то из этого следует, что Земля плоская, а Солнце вращается вокруг неё. В самом деле, фотография Земли из космоса свидетельствует, что земной диск плоский. Тогда земной глобус станет моделью плоской Земли, картой земного диска, для удобства обозрения спроецированной на сферу с подставкой. Кроме того, микробов и вирусов, молекул и атомов, подлости и совести нет, так как их не видно. И такие нелепые выводы следуют из первоначального решения о том, что реальный мир и его образ одно и то же.

Представим, что четыре радиолокационные станции обнаружили в небе над страной, которую они прикрывают, самолёт-шпион. Пусть каждая РЛС сообщила своим управляющим структурам об этом самолёте. Если каждая управляющая структура сообщит главнокомандующему страны о замеченном самолёте, то президент получит четыре разных сообщения из четырёх разных источников. Значит ли это, что и самолётов обнаружено четыре? Если да, то мы всё ещё заблуждаемся, что «сам мир и его образ в нашей голове – одно и то же». Более достоверным же будет ответ, что сам внешний мир (источник образа) и образ мира, отражение мира в головах людей различные вещи. Приведём сравнительную таблицу внизу:

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

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

Есть правильные мысли. Они истинны, т.е. соответствуют дейст-вительности, своим объек-там.hello_html_m6289f0e.png

Есть ложные мысли, они сознательно (умышленно) искажают действитель-ность.

Ещё есть заблуждения - неумышленное искаже-ние действительных свя-зей между объектом и мыслью об объекте. Все мысли, выраженные с помощью языка, называются высказываниями.

Высказывание (суждение) - это изречённая мысль, которая является ответом на вопрос о степени неопределённости наших знаний предмета вопроса. Мысль всегда изрекается о чём-то или о ком-то. Когда мысль изрекается о самой себе, она становится парадоксальной.

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

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

Не все выражения естественных языков являются высказываниями:

1. ППП, высказывающееся о самом себе:

2. Риторический вопрос: суждение выражается в грамматической форме вопроса, ответ на который подразумевается заранее известным:

Ребята! Не Москва ль за нами?”

2. Любой вопрос, исключая риторический.


Как пройти в библиотеку?”

3. Восклицательное предложение:


Как хороши, как свежи были розы!”

3. Побудительное предложение (приказ, императив): “Пшёл вон!”

Говори кратко. Проси мало. Уходи быстро.” (Пётр I).

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

Логическое выражение (ЛВ) - это высказывание, по поводу которого можно заключить, истинно оно или ложно. ЛВ, подобно математическому выражению, вычисляется (выполняется), но в результате получается не число (сумма, разность и др.), а логическое значение - истина (true) или ложь (false). ЛВ - всегда ответ на вопрос: “Истинно ли данное высказывание?”.

Код логической величины true = 1, а логической величины false = 0, поэтому для логических величин истинно неравенство true>false (1>0). Кроме того, в качестве логических выражений используются логические смысловые связки “не”, “и”, “или”, “если..., то...” и некоторые другие. Это служебные слова, которые выполняют роль знаков логических операций, операторов.

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

  • «логическое значение пропозициональной переменной» (её состояние – Истинность или Ложность, логическая 1 или логический 0);

  • «логическая переменная» (операнд, то с чем работает оператор);

  • «логический оператор» (то, что обрабатывает операнды).

________________

(aVb)

2.Конъюнкция (логическое умножение)

И

AND

ab

a&b

ab

3.Слабая дизъюнкция

(логическое сложение)

ИЛИ

OR

aVb

4.Импликация (условный оператор)

ЕСЛИ..., ТО...

IF...THEN...

ab

ab

5. Логическое равенство (эквиваленция)

равно

EQUAL TO

ab

ab

Выражения, содержащие логические операции булевой алгебры1, называются сложными логическими выражениями. Отрицание - одноместная (унарная, от лат. unarius - единичный) операция, применяется к одной логической величине (к одному логическому операнду). Все иные (логические сложение, умножение) двух- и более местные, они связывают между собой минимум две логические величины (два операнда), исключая отрицание. Их называют бинарными (binariusлат. двойной), тернарными (ternariusлат. тройной), тетрарными (tetrariusлат. четверичный) и т.п.hello_html_m549ddbd0.jpg

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

2. Символическая логика. Семантика логических операторов.

2.1. Оператор инверсии (отрицания).

Что делает этот оператор? Он изменяет значение логической переменной на противоположное истину на ложь, а ложь – на истину.

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

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

Для инверсии (отрицания) семантическая таблица строится так:

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

Очевидно, что столбцы I и III совпадают между собой по логическим значениям, как совпадают между собой столбцы II и IV. Теперь можно сформулировать правило вычёркивания: если в логическом выражении встречается несколько отрицаний подряд и между ними нет скобок, то их можно попарно вычёркивать.

В русском языке правило вычёркивания можно применять к предложениям: ведь сказать «Он держал себя не без достоинства» то же самое, что сказать «Он держался достойно». В содержательном плане инверсии соответствует вывернутая рубашка, обманутый обманщик. Так, на карнавале можно делать всё, что нельзя в будние дни.

Следует помнить, что в логике высказываний субъектно-предикатная структура суждений игнорируется, и отрицание должно применяться ко всему высказыванию, а не к его частям. Если неверно (ложно) утверждение «Верно, что все розы красные», то истинно (верно) только утверждение «НЕверно, что все розы красные». Утверждение «Все розы НЕ красные» также будет ложно, поскольку в таком высказывании отрицается лишь предикат суждения, а должно инвертироваться всё высказывание как единое целое.

В описании работы технических устройств (аппаратной реализации логических контуров) семантические таблицы заполняются по правилам, описанным выше, за одним исключением: заполнение логических значений переменной идёт сверху вниз от логических нолей к логическим единицам. Следовательно, матрица семантической таблицы инверсии будет выглядеть иначе (сравните таблицы на этой и следующей страницах). Оба способа записи (И/Л-

таблица и 1\0-таблица) идентичны друг другу, но матрица логических значений одного «опрокинута» для другого.

Иногда для записи и выявления отношений объёмов классов предметов, о которых произносятся высказывания, используются диаграммы Эйлера2-Венна3, т.е. к логике высказываний применим hello_html_m36ef3a9e.jpghello_html_m508dcb2d.pnghello_html_m1551d8b1.jpg

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

Пусть переменная а - класс «зелёные яблоки». Тогда дополнением к нему будет aНЕзелёные яблоки»). Вместе класс а и дополнение к нему a исчерпывают родовое понятие (класс, множество) «яблоки», т.е. а +a 1. Или, что то же самое, но более привычно:

зелёные яблоки + НЕзелёные яблоки = ЯБЛОКИ

Введём правила для закраски областей универсума рассуждения. Будем заливать цветом только ту область, которая соответствует логической единице (истине) в выходном столбце. Высказывание a истинно тогда и только тогда, когда операнд а ложен. Следовательно, внутри круга а краски быть не должно, а за его границами внутри универсума рассуждения должен быть цвет.


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

2.2. Оператор логического умножения (конъюнкция, логическое «И»).

Что делает: бинарный оператор соединяет между собой два класса предметов, и от этого соединения образуется новый (третий) класс-потомок, совмещающий в себе признаки исходных классов-предков. Он отображает соединение, единство, связь двух (или более) вещей в действительности или в наших мыслях о действительности.

В русском языке выражается союзами «…и...»; “..., но...”; «..., а...»; “..., да и...”; «..., а и...»; “..., но и ...”; «не только..., но и ...»; “…, хотя…”; «…, который…»; “…, зато …”; «…, однако…»; “как…, так и …”. Знаки препинания, такие, как запятые, точки с запятой, тире, точки в конце предложений конъюнктивно (от лат. conjunctio – я соединяю) соединяют их в связный текст. Т.е. можно считать, что предложения текста логически умножаются друг на друга.

Составим семантическую таблицу для логического умножения. Пусть

а = «Жених явился»; b – «Невеста явилась»; a&b = ab = «Брак возможен». Заполнение семантической таблицы для конъюнкции по сравнению с оператором инверсии будет более сложным. В операции участвуют два операнда, у каждого может быть два состояния, стало быть, надо рассмотреть все их возможные сочетания по истине и лжи. Если заменить логические значения наличием или отсутствием фигурок жениха или невесты в соответствующих столбцах, получим идентичные по смыслу табличные записи. В отечественной традиции логическое умножение пишется заглавной греческой «лямбдой» (), применим эту запись к И/Л-таблице. В учебной литературе конъюнкция чаще обозначается амперсендом (&), применим такую запись к 1\0-таблице.

&

hello_html_m5d3fa1f7.png

hello_html_m4814d637.png


И

И

И

0

0

0

0

0



Брак

невозможен

hello_html_m5d3fa1f7.png


Брак

невозможен

И

Л

Л

0

0

0

1

0


hello_html_m4814d637.png

Брак

невозможен


hello_html_m4814d637.png

Брак

невозможен

Л

И

Л

1

1

1

0

0

hello_html_m5d3fa1f7.png


Брак

невозможен



Брак

невозможен

Л

Л

Л

1

1

1

1

1

hello_html_m5d3fa1f7.png

hello_html_m4814d637.png


Теперь наглядно представлено «опрокидывание» матрицы И/Л-таблицы в 1\0-таблицу (или, если угодно, наоборот, 1\0-таблицы в И/Л-таблицу). Очевидно, что выбираемый способ записи зависит от предпочтений человека и не меняет смысла употребляемого оператора.

Примеров соединений разных вещей можно привести достаточно много. Если поместить натрий в раствор соляной кислоты, начнётся их соединение, причём из раствора выделится водород H2, а на дно жидкости уйдёт соль NaCl. Ясно, что газ и соль непохожи на исходные металл и раствор кислоты по свойствам и внешнему виду.

Если на белый экран навести лучи от жёлтого и синего прожекторов и пересечь часть их площадей, то место пересечения кругов будет выглядеть зелёным. Зелёного цвета не было до начала взаимодействия жёлтого и синего кругов. Очевидно, что в месте пересечения сочетаются разные длины волн электромагнитного излучения и в глазу возникает ощущение цвета иного, чем прежде.hello_html_6b6135c4.png

Если представить, что левый круг – множество отличников, а правый – спортсменов, то «чечевицу» пересечения должно назвать «спортсмены И отличники». Полученный в результате умножения новый класс вещей по объёму (площади) чаще всего меньше исходных (классов-прародителей). Так, точно неизвестно, больше или меньше два множества «кислые яблоки» и «сладкие яблоки» по объёму в целом, нежели множество «кисло-сладкие яблоки».

В алгебре высказываний правило для логического умножения таково: логическое умножение истинно, только если все операнды, участвующие в нём, истинны. Оператор логического умножения может быть бинарным (a&b), тернарным (a&b&c), тернарным (a&b&c&d) и т.д. При любом числе входящих операндов выходной столбец семантической таблицы будет истинным только в одном случае. На схеме слева изображена диаграмма Эйлера-Венна для тернарного оператора логического умножения. Класс вещей, обладающий всеми признаками трёх исходных классов-прародителей, находится в самом центре, в белом выпуклом треугольнике, там, где a b c И.hello_html_m47382645.png

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

hello_html_m1dc2357c.png

В теории множеств операции логического умножения соответствует пересечение классов.

Логическое умножение можно смоделировать с помощью релейно-контактной схемы – пары ключей a и b, соединённых последовательно. Электроток через такое соединение пойдёт, только если замкнуты оба ключа. Рассмотрите соответствие семантической И/Л-таблицы релейно-контактной схеме:

Конъюнктор. При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей логического умножения, используется этот значок слева. На вход а конъюнктора последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b – импульсы 0,1,0,1 (как во втором входном столбце). Внутри устройства сигналы логически перемножаются, и на выходе справа получается последовательность 0,0,0,1 (как в выходном столбце семантической таблицы).


2.3. Оператор логического сложения (слабая дизъюнкция, логическое «ИЛИ»).

Что делает: бинарный оператор логического сложения разъединяет между собой два класса предметов, но не полностью, не до конца. Он выражает собой выбор из нескольких возможностей по принципу «или то, или другое, или то и другое вместе». Оператор «логическое сложение» допускает совместимость операндов, и его называют “неисключающее «ИЛИ»”.

В русском языке выражается союзами «… или ...», “либо …, либо …”, «или…, или оба», “…или если оба”.

Построим семантическую таблицу операндов, соединённых слабой дизъюнкцией (disjunctio – лат. я разобщаю, обособляю, разъединяю). Пусть


a = «Кролик даст Винни Пуху мёда»;

b = «Кролик даст Винни Пуху сгущенного молока»;

aVb = «Винни Пух не голоден»

Вспомним известный диалог Винни Пуха и Кролика из отечественного мультфильма «Винни Пух идёт в гости» режиссёра Ф.Хитрука:




Если неверны оба высказывания (a и b, по первой строке семантической таблицы), то ложно их логическое сложение, т.е. неверно, что «Винни Пух не голоден». Если хотя бы один из операндов (a либо b) истинный, то верно, что «Винни Пух не голоден». aVb истинно и в том случае, если оба операнда истинны (4-я строка семантической таблицы). Вероятно, Кролик хотел сэкономить на угощении и предложил гостю выбор, а Винни Пух знал логику высказываний и сумел обратить вопрос Кролика себе на пользу.

Человечество подразделяется на 4 типа по группам крови в полном соответствии с семантической таблицей логического сложения. Может быть, это является одним из прямых доказательств того, что логика идей определяется логикой (порядком) вещей. Медики выделяют по системе AB0 4 группы крови, обозначаемые буквенными и цифровыми символами. Отсутствие обоих антигенов или антител обозначают цифрой 0. I группа крови содержит только антитела a, b и обозначается 0ab; II группа крови содержит антиген А и антитело b, обозначается Аb; III группа крови содержит антиген В и антитело a, обозначается Вa; IV группа крови содержит только антигены А и В, обозначается АВ0. Можно построить расширенную семантическую таблицу, в которой определим антитело как антипод (отрицание) антигена (A=a, B=b), а пустые клетки обозначают отсутствие того или иного фактора.hello_html_m19ddbe3e.pnghello_html_m21406ee2.png

Очевидно, что столбцы «Антигены» полностью повторяют входные столбцы таблицы логического сложения, а «Группы крови» выходной столбец aVb, если отбросить записи об антителах справа (a, b, 0).


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

жество «спортсмены ИЛИ отличники» войдут все три закрашенных области.

Самостоятельное сравнение диаграмм Эйлера-Венна для логического сложения и логического умножения, составленных по правилам в 2.1., позволит понять, почему множество «красные И зелёные яблоки» по объёму меньше множества «красные ИЛИ зелёные яблоки».

Логическое сложение можно смоделировать с помощью релейно-контактной схемы – пары ключей a и b, соединённых параллельно. Электроток через такое соединение пойдёт, если замкнут хотя бы один из ключей. Рассмотрите соответствие семантической И/Л-таблицы релейно-контактной схеме:
импульсы 0,1,0,1 (как во втором входном столбце). Внутри устройства сигналы логически складываются, и на выходе справа получается последовательность 0,1,1,1 (как в выходном столбце семантической таблицы).


2.4. Оператор импликации (условный оператор).

Что делает: бинарный оператор импликации соединяет между собой два высказывания (явления) как причину и следствие, выражает связь между достаточным условием и его последствием. Наличие события, о котором говорится в а, является достаточным основанием для того, чтобы имело место событие, указанное или мыслимое в b. Операнд а в такой операции называется антецедентом (от лат. antecedent – предшествующий), операнд b – консеквентом (от лат. consequens – последующий).

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

В русском языке выражается союзами «если…, то...», “всегда, если …, то …”, «a включает b», “если …, тогда …”, «a есть достаточное условие для b», “когда…, тогда…”, «при наличии А всегда имеет место В», “А влечёт В”, «А, значит, В», “из А следует В” и т.д.

Составим семантическую таблицу импликации (от лат. implicite – тесно связываю). Пусть

а = «Зерно посадили в тёплую влажную почву»;

b = «Зерно проросло»;

ab = «Если зерно посадить в тёплую влажную почву, то оно прорастёт».

Разберём теперь возможные сочетания операндов по истинности-ложности построчно. hello_html_4839bdfe.png

Первая строка. Допустим, что зерно посадили в тёплую влажную почву и оно проросло. Так люди практиковали по весне миллионы раз, и в подавляющем большинстве случаев посеянные зёрна прорастали. Операция посева семян стала восприниматься как причина прорастания зерна. В рассмотренном случае условный оператор считается истинным.

Вторая строка. Одно из зёрен посадили в тёплую влажную почву в массе других, а именно оно не проросло (утратило всхожесть). Ясно, что причинно-следственная связь («посадилобязательно взошло») в данном случае не срабатывает. И это связано с течением объективных процессов в мире, внешнем для нашей головы. Ведь сами процессы протекают независимо от наших мыслей о них! В этом случае условный оператор считается ложным.

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

Четвёртая строка. Зерно никуда не помещали, оно лежит как стратегический запас, как страховка на будущую весну на случай заморозков, уничтожающих посевы. Зерно не прорастает потому, что не созданы достаточные условия для его проращивания. (Аргумент для лентяев: «Если бы мы отсеялись, зерно проросло бы»). Нет причины – нет следствия. И в этом случае условный оператор считается истинным.

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

Примеры импликативных высказываний в русском языке: «Лекция кончилась, и студенты разошлись», “Если я буду молчать, я никогда не начну”, «Мне это не нравится, значит, это никуда не годится», “Щёлкни кобылу в нос – она махнёт хвостом”, «Всегда, когда я хочу тебя навестить, тебя нет дома».

Построим для импликации диаграмму Эйлера-Венна по принятым правилам:

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

Каждая пропозициональная переменная в двузначной логике либо истинна, либо ложна, но не то и другое вместе. Число сочетаний двух таких пропозициональных переменных будет 222= 16, т.е. два высказывания можно связать шестнадцатью разными способами.

Введём правила построения сводной И/Л-таблицы. В первой строке запишем восемь раз «Истина» и восемь раз «Ложь». Во второй строке четыре раза «Истина» и четыре раза «Ложь» дважды. В третьей строке – дважды «Истина» и дважды «Ложь» четыре раза. В четвёртой строке – «Истина», затем «Ложь» восемь раз подряд.

Для построения сводной 1\0-таблицы первую строку надо заполнить восемь раз нолями и восемь раз единицами. Во второй строке – дважды по четыре ноля и по четыре единицы. В третью строку внесём четырежды два ноля и две единицы. В четвёртой строке попеременно восемь раз 0 и 1. Следует добавить к этой таблице строку с номерами логических функций от F1 до F16 включительно.

В дальнейшем все иные способы записи логических операторов будем упорядочивать по сводной таблице 1\0. Следует обратить внимание на то, что операторы в И/Л- и 1\0-таблицах стоят на разных местах.

Константа «всегда истина»

Слабая дизъюнкция

Репликация

Переменная А

Импликация

Переменная В

Равносильность

Конъюнкция

Штрих Шеффера

Исключающая дизъюнкция

Отрицание переменной В

Антиимпликация

Отрицание переменной А

Антирепликация

Стрелка Пирса

Константа «всегда ложь»

И

V

А

В

V

B


A

Л

И

И

И

И

И

И

И

И

Л

Л

Л

Л

Л

Л

Л

Л

И

И

И

И

Л

Л

Л

Л

И

И

И

И

Л

Л

Л

Л

И

И

Л

Л

И

И

Л

Л

И

И

Л

Л

И

И

Л

Л

И

Л

И

Л

И

Л

И

Л

И

Л

И

Л

И

Л

И

Л

Альтернативные знаки





&





























~










Константа

«всегда ложь»

Конъюнкция

Антимпликация

Переменная А

Антирепликация

Переменная В

Исключающая дизъюнкция

Слабая дизъюнкция

Стрелка Пирса

Равносильность

Отрицание переменной В

Репликация

Отрицание переменной А

Импликация

Штрих Шеффера

Константа «всегда истина»

Л

&


А

В

V

V

B

A

И

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

Функции F4 и F13, F6 и F11 являются переменными А, В и их отрицаниями. Функции F1 и F16 являются логическими константами: F1 есть выходной столбец тождественно-ложных формул (противоречий), F16 – выходной столбец для тождественно-истинных формул (законов или тавтологий).


2.6. Логическое равенство (эквивалентность, равносильность).

Что делает: бинарный оператор логического равенства считается истинным, если два составляющие его операнда совпадают по своим логическим либо оба вместе истинны, либо оба вместе ложны. Эквивалентная связь двух явлений такова, что существование первого обусловлено существованием второго, и наоборот. Например, дедушкой или бабушкой можно быть только при наличии хотя бы одного внука (одной внучки). Пока нет внуков, человек не может считаться дедушкой (бабушкой).hello_html_m7d70d773.jpg

В русском языке выражается союзами «тогда и только тогда, когда….», “точно тогда, когда”, «… если и только если …», “если…, то… и обратно”, «для того, чтобы …, необходимо и достаточно …», “эквивалентно” (от лат. aequivalens – равносильный, равноценный, равнозначный).

Например, гражданин становится совершеннолетним тогда и только тогда, когда он достиг 18 лет.

Эквиваленция в диаграммах Эйлера-Венна выглядит так:hello_html_mb2707ca.png

hello_html_63e556f8.jpg







Оператор равносильности используется при замене одних логических операторов и формул другими.

Порядок формальных доказательств с помощью семантических таблиц:

  1. Расставить номера операторов в порядке приоритета слева, а затем справа от логического равенства. Оно выполнится в последнюю очередь.

  2. Определить количество участвующих операндов n и заполнить входные столбцы константами «Истина» и «Ложь» по формуле 2n=N. По ней в семантической таблице из двух операндов нужны четыре строки, для трёх – восемь и т.д.

  3. Выполнить операторы согласно расставленным номерам.

К примеру, требуется доказать, что 1) ab aVb; 2) (aVb) a&b

Доказательства с помощью таблиц истинности:

2.7. Логическое неравенство (строгая дизъюнкция).

Что делает: бинарный оператор строгой дизъюнкции выражает тот факт, что одна из имеющихся возможностей исключает все остальные. Это альтернатива либо того, либо другого варианта развития событий. Строго-разделительная дизъюнкция означает такую связь двух операндов, при которой наличие одного из дизъюнктов полностью исключает всё то, что может принадлежать (мыслиться) другому дизъюнкту.hello_html_52d823be.jpg

В русском языке выражается союзами «либо…, либо…», “или…, или…”, выражениями «желательно…, но невозможно», “либо так, либо никак”.

Примеры: «Электрический ток бывает или постоянный, или переменный». «Хоть видит око, да зуб неймёт». «Этот человек зряч или слеп».

Правило для строгой дизъюнкции: она истинна, когда истинен только один из операндов, в ней участвующий.


Диаграмма Эйлера-Венна для логического неравенства выглядит так:

Попытка выразить строгую дизъюнкцию с помощью релейно-контактных схем требует некоего трюка: понадобятся две пары ключей, соединённых параллельно. Добавим в семантическую таблицу рядом со входными столбцы a и b. Это не изменит результата операции, но свяжет таблицу со схемами. Исследование таблицы показывает нам, что ключи связаны попарно таким способом: если ключ a (b) открыт, то его антипод a (b) закрыт, и наоборот.


Первой строке расширенной семантической таблицы логического неравенства соответствует релейно-контактная схема:

Очевидно, что ключи a и b разомкнуты, и ток по цепи пройти не может


Случай для второй строки: ток по цепи пройдёт по ключам b и а.

Для третьей строки: ток по цепи пройдёт по ключам a и b.

Четвёртая строка таблицы показывает, что ток по цепи не пойдёт:

Расширенная таблица не отражает (и не должна!) ещё нескольких случаев для релейно-контактных схем. В приведённых ниже вариантах вторая пара ключей оказывается излишней, и схема может быть упрощена до слабой дизъюнкции (можно отбросить любую пару):

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


2.8. Штрих Шеффера (исключающее «ИЛИ», эксклюзия).

Что делает: бинарный оператор исключающего «ИЛИ» выражает тот факт, что одно высказывание исключает другое, что a и b несовместимы по истинности. Эксклюзия в принципе допускает, что a и b могут быть ложными вместе.

В русском языке выражается союзами «то ли …, то ли ...». Человек мог родиться или в Перми, или в Кунгуре (ясно, что в двух местах сразу родиться невозможно, но можно родиться в каком-либо третьем). «Первая пара сегодня будет или физикой, или физкультурой» (а может быть, и какой-то другой).

Диаграмма Эйлера-Венна для функции Шеффера выглядит так:

По своему содержанию штрих Шеффера является антиконъюнкцией, отрицанием логического умножения. Тогда будут равносильными формулы:
ab (a&b). Доказательство с помощью семантической таблицы предлагается провести самостоятельно.

Логический контур «и-НЕ». При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей штриха Шеффера, используются значки слева или справа. Рассмотрим левый логический контур. На вход а контура «и-НЕ» последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b – импульсы 0,1,0,1 (как во втором входном столбце). Внутри конъюнктора сигналы логически умножаются, затем сигнал с выхода конъюнктора попадает в инвертор, и на выходе справа получается последовательность 1,1,1,0 (как в выходном столбце семантической таблицы). В правой схеме инвертор «вдвинут», встроен в выход конъюнктора.hello_html_227397c1.pnghello_html_59f3728a.png

2.9. Стрелка Пирса.

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

В русском языке выражается союзами «ни … ни ...». В английском – конструкцией “neithernor…”.hello_html_m233d7a86.jpg

Оператор ab читается «ни a, ни b». Впервые исследован и введён в науку Чарльзом Пирсом4 в конце XIX в. Примеры: «Ни рыба ни мясо». «Стоял в поле теремок ни низок ни высок». «Не в силах я жить ни с тобой, ни в разлуке с тобой» (Овидий). «Когда человек не хочет знать правды, то ни доводы разума, ни добрые советы не помогут».


По содержанию стрелка Пирса является антиподом логического сложения, отрицанием слабой дизъюнкции. Тогда будут равносильны формулы: ab (a V b). Доказательство с помощью семантической таблицы предлагается провести самостоятельно.hello_html_m30afabdd.jpg







Диаграмма Эйлера-Венна для стрелки Пирса выглядит так:

Рассмотрим левый логический контур. На вход а контура «или-НЕ» последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b – импульсы 0,1,0,1 (как во втором входном столбце). Внутри дизъюнктора сигналы логически умножаются, затем сигнал с выхода дизъюнктора попадает в инвертор, и на выходе справа получается последовательность 1,0,0,0 (как в выходном столбце семантической таблицы). В правой схеме инвертор «вдвинут», встроен в выход дизъюнктора.


2.10. Репликация

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

В русском языке выражается союзами «только если …, то ...», высказыванием «А реплицирует В».

Поскольку a b b a, то репликацию иногда называют обратной импликацией. Примеры репликативной связи высказываний: «Если человек тратил деньги, то он их имел»; «Только если замкнут контакт, лампочка горит»; «Люди перестают мыслить, когда перестают читать»; «Я растратил душу по кусочкам, а она была, была, была!..»hello_html_39c91e43.jpg

В реальной жизни достаточно часто приходится умозаключать от консеквента: если человек оставил отпечатки пальцев на месте преступления (b), значит, он там был (a). Противоречит такому умозаключению следующее: человек не был на месте преступления (a), а его отпечатки пальцев есть (b). Такая ситуация отображена в третьей строке семантической И/Л-таблицы (во второй строке 1\0-таблицы).

Диаграмма Эйлера-Венна для репликации выглядит так:

2.11. Антиимпликация и антирепликация.

Операторы под именами F3 и F5 характеризуют антиимпликацию и антирепликацию. Антирепликация обозначается как , читается «не А, а В». Например, «Классик не подлежит критике, но подлежит исследованию» (М. Шагинян). «Не транжирить народное богатство, а приумножать его».

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

Очевидно, что будет равносильна формула: (a b) a b, то же верно и для пары «импликация – антиимпликация».


3. Доказательства логических равенств с помощью семантических таблиц.

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

Докажем, что выражение a&aЛ, и выражение aVaИ

Докажем, что равносильны выражения a b и (a&b) для И/Л- и 1\0-таблиц.
Для каждого выражения составлены отдельные семантические таблицы. Столбцы 1 и 2 нет нужды переписывать несколько раз, поэтому таблицы можно совместить, сделав общими начала. Для столбца 3 применены значения операторов отрицания и логического умножения по определению. Для столбца 4 применено правило для импликации (она ложна, только если антецедент истинный, а консеквент ложный) и правило для отрицания (инвертируется то, что в скобке (a&b)). Сократим записи доказательств, удалив повторяющиеся столбцы и оставив нумерацию так, как было выше. Ниже будем сокращать записи по такому же принципу.


a

b

b

ab

a&b

(a&b)



a

b

b

ab

a&b

(a&b)

И

И

Л

Л

И

Л



0

0

1

1

0

1

И

Л

И

И

Л

И



0

1

0

1

0

1

Л

И

Л

И

Л

И



1

0

1

1

0

1

Л

Л

И

И

Л

И



1

1

0

0

1

0

1

2

3

4

3

4



1

2

3

4

3

4

Установим табличным способом, являются ли формулы a(bc) и a&bc равносильными. Для трёх операндов понадобится семантическая таблица из восьми строк. Операции выполним в порядке приоритета.

X


Y


a

b

c

bc

a(bc)

a&b

a&bc

XY

И

И

И

И

И

И

И

И

И

И

Л

Л

Л

И

Л

И

И

Л

И

И

И

Л

И

И

И

Л

Л

И

И

Л

И

И

Л

И

И

И

И

Л

И

И

Л

И

Л

Л

И

Л

И

И

Л

Л

И

И

И

Л

И

И

Л

Л

Л

И

И

Л

И

И

Операции с ними

1

2

3

4

5

Табличный метод доказательства тождества формул является самым надёжным. Но если число операндов более 4-х, становится затруднительным выписывать и сопоставлять столь длинные (32 строки, 64 строки и т.д.) столбцы. Для формализации вычислений вводятся правила операций с операндами, позволяющие сводить сложные высказывания к относительно простым. Таблица функций F1-F16 позволяет заменять одни операции на другие, как это делалось страницей выше. Такие операции проводятся на основе законов алгебры логики.


4. Законы алгебры логики. Правила преобразования логических выражений.

4.1. Закон двойного отрицания: aa (здесь применяется правило вычёркивания).


4.2. Закон коммутативности выражается в том, что результат операции с двумя элементами не зависит от порядка, в каком берутся эти элементы. В общем случае бинарная операция a*b называется коммутативной, если a*b=b*a. (* - любой возможный логический оператор):

Коммутативны шесть логических операций:

4.3. Закон ассоциативности (сочетательный закон) состоит в свободном соединении одного члена с другим или группой других членов, если они связаны одинаковыми логическими операторами. В общем случае тернарная операция a*b*c называется ассоциативной, если a*(b*c)=(a*b)*c=c*b*a.

Ассоциативны шесть логических операций:

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

4.4.1. Дистрибутивность конъюнкции относительно слабой дизъюнкции для трёх переменных распадается на три варианта:

Доказательство всех трёх случаев с помощью электронной таблицы (на примере OpenOffice.org Calc):

hello_html_5761e0ab.png

4.4.2. Дистрибутивность слабой дизъюнкции относительно конъюнкции для трёх переменных распадается на три варианта:

Доказательство всех трёх случаев с помощью электронной таблицы (на примере OpenOffice.org Calc):

hello_html_m70106902.png

4.4.3. Дистрибутивно упорядочены пять пар логических операторов:

4.5. Законы поглощения. Так называются равносильности

и их варианты: Частными случаями законов поглощения являются равносильности: 4.6. Законы идемпотентности (от лат. идемпотентный – сохраняющий ту же силу, способность). Этот закон утверждает, что конъюнкция двух или более тех же самых конъюнктов равносильна самому этому конъюнкту. То же справедливо и для дизъюнкции и составляющих её дизъюнктов. Законы идемпотентности за-

a&aa

aVaa

4.7. Законы отбрасывания (исключения констант) позволяют исключать из формулы тавтологию и логическое противоречие.

4.7.1. Закон исключения тавтологии из конъюнкции: a&(bVb)a

4.7.2. Закон исключения противоречия из слабой дизъюнкции: aV(b&b)a

Они основываются на двух фундаментальных законах логики:

4.8.1. Законе (не)противоречия:

a&aЛ

(иная запись: a&a0)

4.8.2. Законе исключённого третьего:

aVaИ

(иная запись: aVa1)

4.9. Правила зачёркивания посылки:

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

4.12. Законы общей инверсии (Огастеса де Моргана5) позволяют выразить конъюнкцию через слабую дизъюнкцию и отрицание, а слабую дизъюнкцию – через конъюнкцию и отрицание:hello_html_739fad94.jpg

4.13. Закон исключения (склеивания)

Предлагаем доказать данные законы с помощью семантических таблиц (вручную) или с помощью электронных таблиц (на имеющемся программном обеспечении).

5. Функционально полные языки логических операторов.

Сводная таблица логических операторов F1-F16 позволяет нам выражать одни операторы через другие. Например, закон общей инверсии (4.12) позволяет выразить логическое сложение через отрицание логического умножения, а последнее – через отрицание и логическое сложение. Ранее мы уже выражали импликацию через отрицание и логическое сложение. Существуют такие пары операторов или одиночные операторы, которые могут через себя выразить все остальные, оставшиеся в таблице F1-F16.

Людям необходимо множество разных способов для выражения оттенков мыслей. Для вычислительной техники желательны устройства относительно простые и надёжные, унифицированные. Идеальный вариант – когда ЭВМ строится из одного универсального «кирпичика». Это приводит к тому, что высказывания внутри счётного цифрового устройства вырастают в длину. Для человека такой путь неприемлем.

Язык булевой алгебры, позволяющий выразить многообразие сочетаний пары операндов по истинности/ложности с помощью двух (а лучше – одного) операторов, называется функционально полным. В двузначной логике таких языков насчитывается шесть. В фигурных скобках запишем один или два оператор(-а):

{ V}

{ V}

{}

II

IV

VI

{ &}

{ &}

{}

Открытие функционально полных языков (далее - ФПЯ), состоящих из одного оператора, связано с тем, что некоторые из математиков, создававшие их, были глубоко верующими людьми. В теологии распространён постулат о том, что Господу для создания нашего мира из ничто ничего не надо было разрушать (отрицать). Он только творил (утверждал столп бытия). Это значило, что оператор инверсии (отрицания) можно было исключить из конструируемого языка, создать один из вариантов неотрицательной логики. Итак, получен довольно неожиданный вывод о том, что вычислительные машины в какой-то мере были созданы на основе религиозных представлений учёных мужей.

И в самом деле, импликация содержит в своём выходном столбце три утверждения и одно отрицание. По терминологии философов, отрицание в импликации «снято» (скрыто присутствует в логических значениях оператора). То же можно сказать о штрихе Шеффера (одно отрицание и три утверждения в выходном столбце) и о стрелке Пирса (одно утверждение и три отрицания).

В п. 3 настоящего издания мы доказывали, что ab(a&b). Ещё выше было доказано, что abaVb. Это значит, что ФПЯ I можно выразить через ФПЯ III (и наоборот!), ФПЯ II – через ФПЯ IV, ФПЯ I – через ФПЯ II (законы общей инверсии, 4.12.). Осталось доказать, что ФПЯ I, II, III, IV можно выразить через ФПЯ V или ФПЯ VI. Рассмотрим одно из следующих высказываний с помощью семантической таблицы:

aaa

5) a(aa)(aa)

9) a&b(ab)(ab)

2) aaa

6) a(aa)(aa)

10) a&b(aa)(bb)

3) aVb(ab)(ab)

7) (aVb)ab

11) (aVb)[(aa)(bb)][(aa)(bb)]

4) aVb(aa)(bb)

8) (a&b)ab

12) (a&b)[(aa)(bb)][(aa)(bb)]

Докажем, что 1) - 2) и 5)- 6)– попарно эквивалентные высказывания. Для утверждения 1) применим правило для штриха Шеффера: он ложен, когда оба его операнда истинны, в остальных случаях он истинный. Сделаем двумя входными столбцами операнд a. Для утверждения 2) применим правило для стрелки Пирса: она истинна, когда оба её операнда ложны, во всех остальных случаях она ложна. Для утверждений 3) и 4) применим правило: отрицание отрицания есть утверждение.

Докажем, что 3) - 4) – попарно эквивалентные высказывания.
Аналогично можно провести доказательства всех остальных случаев. Итак, действительно, через ФПЯ V и ФПЯ VI можно выразить все остальные операторы их сводной таблицы F1-F16.

6. Логические контуры

Для конструирования устройств компьютера можно применять пять базовых элементов: инвертор, конъюнктор, дизъюнктор, «или-НЕ», «и-НЕ». Совмещая их по правилам ФПЯ I-VI, можно смоделировать работу любого оператора из сводной таблицы F1-F16.


смотрим, какие сигналы поступят на выход этого устройства. Обозначим выход контура через F. Для логического сложения операндов b и c пользуемся правилом: логическое «ИЛИ» истинно, если хотя бы один из операндов истинный. Перемножение результата со столбцом a идёт по правилам логического «И». Выпишем на входах сигналы по первой строке семантической таблицы: a=0, b=0, c=0. Сигналы со входов b, c логически складываются в дизъюнкторе, затем с его выхода поступают на вход конъюнктора вместе с сигналом со входа а. В конъюнкторе поступившие сигналы перемножаются и на его выходе получим 0. Заносим полученные значения в промежуточный и выходной столбцы. Переходим последовательно ко 2-й, 3-й и т.д. строкам семантической таблицы и заполняем промежуточный и выходной столбцы полученными логическими значениями. Таким способом можно наглядно рассмотреть, как проходят логический контур устройства разные сочетания сигналов.

По приведённому логическому контуру построим формулу сложного высказывания и его семантическую таблицу. Определим его имя по сводной таблице логических операторов F1-F16.

Формула сложного высказывания пишется как a&b. В семантической таблице будет два операнда и четыре строки. В таблице понадобится два входных столбца, два промежуточных (для отрицаний) и выходной столбец, перемножающий сигналы с выходов инверторов.

Последовательно пошлём на входы устройства сочетания первой, затем второй и т. д. строк семантической таблицы, заполним промежуточные столбцы результатами действий инверторов. В выходном столбце заносим построчно результат работы конъюнктора. По сводной семантической таблице F1-F16 определяем, что это таблица функции «стрелка Пирса» (F9). Следовательно, данный нам логический контур моделирует работу по схеме логического оператора «или-НЕ».

Предлагаем самостоятельно исследовать работу контуров, приведённых ниже и опознать их по именам таблицы F1-F16.


hello_html_m5be7e852.png

hello_html_3a06c2d1.png

hello_html_45cf2cef.png

hello_html_m39df099f.png

hello_html_51e6c629.png

hello_html_m750fe4fc.png

hello_html_58330df3.png

hello_html_m1b9beb89.png

hello_html_m5e095d4c.png

hello_html_1f95943a.png

hello_html_mb77080c.png

hello_html_mab8a7ee.png

hello_html_f223a5a.png

hello_html_m76043b7a.png

hello_html_227397c1.png

hello_html_65b2e684.png

hello_html_5bfbdb20.png

hello_html_6d81910e.png

Устройства внизу таблицы сделаны из однотипных логических элементов в соответствии с уже изученными формулами: (aa)(bb); (aa)(bb). Сигналы на входы верхнего и нижнего устройств поступают в соответствии с сочетаниями входных столбцов a и b.

7. Сводная таблица диаграмм Эйлера-Венна для F1-F16

Ниже приводится таблица, содержащая диаграммы Эйлера-Венна ко всем операторам (функциям) таблицы F1-F16.

F1

hello_html_m218e0291.png

F2

hello_html_m1dc2357c.png

F3

hello_html_m14808a44.png

F4

hello_html_b9a46e7.png

F5

hello_html_m1f0da919.png

F6

hello_html_m5fec52c7.png

F7

hello_html_687de718.png

F8

hello_html_m6440255d.png

F9

hello_html_76501ee0.png

F10

hello_html_m6a420f7b.png

F11

hello_html_m17d66dc2.png

F12

hello_html_m313cf57f.png

F13

hello_html_795407b3.png

F14

hello_html_ec45396.png

F15

hello_html_m48d663d1.png

F16

hello_html_m37ef0f99.png


8. Триггер – структурная единица (ячейка) памяти ЭВМ.

Электронная схема устройства разработана в 1918 г. известным русским радиотехником М. А. Бонч-Бруевичем и независимо от него в 1919 г. американскими специалистами У. Икклзом и Ф. Джорданом. Рассмотрим простейшее устройство с двумя раздельными входами (RS-триггер). Эта схема составлена из двух вентилей «или-НЕ» (стрелок Пирса). Работа выхода P описывается уравнением P(SVQ), выхода Q – уравнением Q(PVR).

et

Reset

P

Q

Состояние
триггера

0

0

1

0

Хранение

бита

0

1

0

1

1

0

Запоминает

0

1

0

0

1

Запоминает

1

1

1

0

0

Комбинация

не сохраняется


Неустойчивое состояние: при действии входных импульсов на обоих входах (S=1, R=1) выходы определяются однозначно, но после прекращения действия входных импульсов такая комбинация входных величин сохраниться не может, и эта комбинация входных импульсов именуется запрещённой.

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

Если на входы этого триггера подать S=1, R=0, то (независимо от состояния Q) на выходе Р верхнего вентиля появится 0. После этого на входах нижнего вентиля окажется R=0, P=0 и выход Q станет равным 1.

Если теперь перестать подавать сигналы на триггер (S=0, R=0), то, поскольку входами верхнего вентиля являются S=0, Q=1, его выход Р останется 0. Аналогично, поскольку входами нижнего вентиля являются R=0 и Р=0, его выход Q по-прежнему будет 1. Таким образом, установленные значения выходов P и Q не изменятся при переходе к S=0, R=0.

Точно так же при подаче S=0, R=1 на выходах появятся Q=0, P=1 и эти значения входов сохранятся, если перестать подавать 1 на вход R (R=0, S=0). Подача сигнала на вход R позволяет вернуть триггер к исходному (нулевому) состоянию.

При отсутствии импульсных сигналов на обоих входах (S=0, R=0) выходные величины определяются неоднозначно: P=0, Q=1 либо P=1, Q=0. Это значит, что, пока на триггер не поступает входных импульсов, устройство сохраняет запомненную комбинацию.

Таким образом, при R=0, S=0 триггер на элементной базе «или-не» может находиться в двух разных состояниях: Q=1 и Q=0. Выход Q и является значением запомненного бита.

Если собрать триггер из элементов «и-не» (штриха Шеффера), то получим иное распределение на выходах устройства

et

Reset

P

Q

Состояние
триггера

0

0

1

1

Комбинация

не сохраняется

0

1

1

0

Запоминает

0

1

0

0

1

Запоминает

1

1

1

0

1

Хранение

бита

1

0

Хотелось бы обратить внимание учащихся на то, что в учебном издании [6, С.61-62] при описании работы триггера допущены ошибки и неточности. Предлагается найти их самостоятельно.

9. Полусумматор двоичных чисел.

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

Работа этого устройства описывается для выхода Р уравнением Px&y, для выхода S – уравнением S(xVy)&(x&y).

Построив таблицу истинности для выражения S, получим:

Изучение столбцов P и S показывает нам, что на входы x, y можно посылать двоичные сигналы 0 и 1 и получать на выходах коды двоичных чисел 002, 012, 102. Полусумматор умеет складывать поступающие сигналы по правилам таблицы сложения для двоичной системы счисления и переносить результат сложения двух единиц в соседний (старший) разряд моделируемого двоичного числа.


10. Сумматор на три входа (полный сумматор)

Сумматор на три входа (полный сумматор) назван так потому, что он может складывать три двоичных сигнала и выдавать на выходе сочетания 002, 012, 102, 112. Работа выхода Q определяется формулой x&PVy&PVx&y. Работа выхода S определяется формулой (QVx&y&P)&(xVyVP) (или Q&(xVyVP)Vx&y&P). Слева и внизу от таблицы, описывающей работу контуров, представлены разные схемы сумматора на три входа. Изучение работы сумматора на три входа по любой схеме показывает нам, что ему «безразлично», с какого входа в него поступают обрабатываемые сигналы. Логический контур внизу составлен из двух полусумматоров, к которым добавлен дизъюнктор. Изучение работы любого из устройств любым знакомым Вам способом докажет, что обе схемы работают одинаково.

x

y

P

Q

S

0

0

0



0

0

1



0

1

0



0

1

1



1

0

0



1

0

1



1

1

0



1

1

1















hello_html_m683c8799.png

11. Шифратор.


Для того, чтобы понять, каким способом кодируются символы при вводе в компьютер, рассмотрим работу клавиатуры микрокалькулятора, а именно – его цифровые клавиши. Слева изображены кнопки цифр от 0 до 9. Нажимая на одну из них, человек замыкает цепь, посылая по контактному проводу сигнал на дизъюнкторы P, или Q, или R, или U. Предлагается самостоятельно рассмотреть работу шифратора при помощи такой таблицы: Нажата

кнопка

P

Q

R

U

0





1





2





3





4





5





6





7





8





9






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


12. Аппаратная реализация логических контуров на базе МОП-транзисторов.

В радиоаппаратуре транзи-сторы чаще всего исполь-зуются для усиления плавно меняющихся (аналоговых) сигналов. В вычислитель-ной технике транзисторы используются в т. наз. клю-чевом режиме. В этом режиме транзистор можно представлять как обычный выключатель, который в одном положении проводит ток (замкнут), а другом – нет (разомкнут). В отличие от бытового выключателя включение и выключение транзистора производится также с помощью электричества. Существует много типов транзисторов. Рассмотрим некоторые логические схемы на базе МОП-транзисторов (металл-оксид-полупроводник). Каждый МОП-транзистор имеет 4 контакта: сток, исток, затвор и подложку.hello_html_m64389afe.pnghello_html_m5f86f5c3.png

Nканальный транзистор проводит ток между истоком и стоком (замкнут), только если на затвор подано положительное (относительно подложки) напряжение.

P-канальный транзистор проводит ток, только если напряжение на затворе меньше напряжения на подложке.

12.1. Вентиль «НЕ» (инвертор)

Рассмотрим последовательно работу вентиля «НЕ», посылая на вход высокий, а затем низкий уровни напряжения (+5 В и 0 В). Очевидно, что вход и выход таблицы выше соответствует таблице, описывающей работу инвертора.


12.2. Вентиль «или-НЕ» (стрелка Пирса)

Стрелку Пирса можно собрать из четырёх МОП-транзисторов: двух р-канальных (вверху (I) и в середине (II)) и двух n- канальных (внизу справа (III) и слева (IV)).hello_html_m4be3f91c.png

Для изучения работы вентиля «или-НЕ» необходимо описать с помощью таблицы 4 состояния вентиля при различных сочетаниях сигналов, посылаемых на входы 1 и 2. Рекомендуется самостоятельно исследовать работу предъявленного вентиля на следующей странице пособия. Образец для заполнения таблиц дан внизу.




Сочетание входных сигналов 1

Вход 1

I транзистор (p-канальный)

II транзистор (p-канальный)

Выход

затвор

подложка

состояние

затвор

подложка

состояние

0 В

0 В

+5 В

замкнут

0 В

+5 В

замкнут

+5 В

Вход 2

III транзистор (n-канальный)

IV транзистор (n-канальный)

затвор

подложка

состояние

затвор

подложка

состояние

0 В

0 В

0В В

разомкнут

0 В

0 В

разомкнут




Сочетание входных сигналов 2

hello_html_4cec6bb9.png


Вход 1

I транзистор (p-канальный)

II транзистор (p-канальный)

Выход

затвор

подложка

состояние

затвор

подложка

состояние









Вход 2

III транзистор (n-канальный)

IV транзистор (n-канальный)

затвор

подложка

состояние

затвор

подложка

состояние








Сочетание входных сигналов 3

hello_html_6e130583.png


Вход 1

I транзистор (p-канальный)

II транзистор (p-канальный)

Выход

затвор

подложка

состояние

затвор

подложка

состояние









Вход 2

III транзистор (n-канальный)

IV транзистор (n-канальный)

затвор

подложка

состояние

затвор

подложка

состояние









Сочетание входных сигналов 4

hello_html_m3c3dfd6.png


Вход 1

I транзистор (p-канальный)

II транзистор (p-канальный)

Выход

затвор

подложка

состояние

затвор

подложка

состояние









Вход 2

III транзистор (n-канальный)

IV транзистор (n-канальный)

затвор

подложка

состояние

затвор

подложка

состояние









Сводная таблица состояний вентиля «или-НЕ» (стрелки Пирса из 4-х МОП-транзисторов)

Список литературы:


1. Берков В.Ф. и др. Логика: Учебное пособие/ В. Ф. Берков, Я.С. Яскевич, В.И. Павлюкевич – Мн: НТООО «ТетраСистемс», 1997.

2. Введение в информатику. Лабораторные работы/ Авт.-сост. А. П. Шестаков. – Пермь, 1999.- Часть I.

3. Гутер Р.С., Полунов Ю.Л. Математические машины. Очерки вычислительной техники. Пособие для учителей. М., «Просвещение», 1975.

4. Информатика. Введение в логику/ Сост. Н. Г. Иванова, О. Л. Русакова. – Пермь: Изд-во Перм. ун-та, 2000.

5. Как могут быть связаны два высказывания: Методические указания по изучению курса логики/ Перм. ун-т: Сост. В. Х. Зеленкин. – Пермь, 1992.

6. Колмыкова Е.А. Информатика: учеб. пособие для студ. сред. проф. образования /Е.А. Колмыкова, И.А. Кумскова.- 2.е изд., стер.- М.: Издательский центр «Академия», 2006.

7. Кушниренко А.Г. и др. Основы информатики и вычислительной техники: Проб. учеб. для сред. учеб. заведений/ А. Г. Кушниренко, Г. В. Лебедев, Р. А. Сворень.- М.: Просвещение, 1990.

8. Кэрролл Л. Логическая игра: Пер. с англ. Ю.А. Данилова.- М.: Наука. Гл. ред. физ.-мат. лит., 1991.

9. Логика высказываний: Методические указания по изучению курса логики/ Перм. ун-т: Сост. В.Х. Зеленкин. – Пермь, 1998.

10. Лыскова В.Ю., Ракитина Е.А. Логика в информатике. – М.: Лаборатория Базовых Знаний, 2001.

11. Ляхович В.Ф., Крамаров С.О. Основы информатики. Изд 3-е. – Ростов-н/Д: изд-во «Феникс», 2003.

12. Мнеян М.Г. Физические принципы работы ЭВМ: Кн. для внеклас. чтения учащихся 8-10 кл. сред. шк. – М.: Просвещение, 1987.

13. Примерная программа учебной дисциплины "Информатика". - М.: Издательский отдел ИПР СПО, 2003 - 20 с.

14. Светлов В.А. Практическая логика. – СПб.: Изд-во РХГИ, 1995.

15. Свойства логических операций и взаимозаменяемость логических союзов: Методические указания по изучению курса логики/ Перм. ун-т: Сост. В.Х. Зеленкин. – Пермь, 1992.

16. Семененко В.А., Балтрушевич А.В. Электронно-вычислительные машины: Учеб. пособие для сред. ПТУ. - М.: Высш. шк., 1985.

17. Тигриная алгебра. Пересказ А. Куликова. – М.: Багира, 1994.

18. Угринович Н.Д. Информатика и информационные технологии: Учебное пособие для общеобразовательных учреждений.- М.: Бином: 2001. Приложение к учебнику (CD-ROM)/Практикум/Основы логики.

19. Формальная логика. – Л.: Изд-во Ленингр. ун-та, 1977.

20. Язык как знаковая система: Методические указания по изучению курса логики. Перм. ун-т: Сост. В.Х. Зеленкин. – Пермь, 1994.

1БУЛЬ Джордж (George Boole) (2 ноября 1815, Линкольн, Великобритания — 8 декабря 1864, Баллинтемпль, Ирландия), английский математик и логик, один из основоположников математической логики. Разработал алгебру логики (булеву алгебру) («Исследование законов мышления», 1854), основу функционирования цифровых компьютеров.

2 ЭЙЛЕР (Euler) Леонард (1707-83), российский ученый — математик, механик, физик и астроном. По происхождению швейцарец. В 1726 был приглашен в Петербургскую АН и переехал в 1727 в Россию. Был адъюнктом (1726), а в 1731-41 и с 1766 академиком Петербургской АН (в 1742-66 иностранный почетный член). В 1741-66 работал в Берлине, член Берлинской АН. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, баллистике, кораблестроению, теории музыки и др.

3 ВЕНН (Venn) Джон (1834-1923), английский логик, разработал графический аппарат диаграмм, фактически эквивалентный логике классов. Труды в области вероятностной и индуктивной логики.

4ПИРС Чарльз (полн. Чарльз Сандерс Пирс, Charles Sanders Peirce) (10 сентября 1839, Кембридж, Массачусетс — 19 апреля 1914, близ Милфорда, Пенсильвания) — американский философ, логик, математик и естествоиспытатель. Родоначальник прагматизма, Пирс выдвинул принцип, согласно которому содержание понятия целиком исчерпывается представлением о его возможных последствиях. Основатель семиотики, автор работ по математической логике.

5 МОРГАН (De Morgan) Огастес (Августус) де (1806-71), шотландский математик и логик. Труды по алгебре, теории рядов. Независимо от Джорджа Буля пришел к основным идеям математической логики.

Курс профессиональной переподготовки
Учитель информатики
Курс профессиональной переподготовки
Учитель математики и информатики
Найдите материал к любому уроку,
указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Общая информация

Вам будут интересны эти курсы:

Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Облачные технологии в образовании»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.