82342

Разработка программы построения таблицы истинности логической функции

Дипломная

Информатика, кибернетика и программирование

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

Русский

2015-02-27

155 KB

14 чел.

ГБОУ Гимназия № 1505

«Московская городская педагогическая гимназия – лаборатория»

ДИПЛОМ

Разработка программы построения

таблицы истинности логической функции

автор: Сазонова Виктория, 10  класс «Б»

руководитель: Г.А.Пяткина. 

Москва

2012

СОДЕРЖАНИЕ

Введение

1. Алгебра логики

1.1. Понятие алгебры логики. Основные логические операции

1.2. Логические выражения. Таблицы истинности

1.3. Алгебра логики в компьютерах

2. Законы алгебры логики и их доказательство

3. Практическая часть. Разработка программы. Описание  работы программы

Заключение

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

Приложения

Введение

Актуальность исследования.

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

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

Цель работы: разработать программу для построения таблиц истинности заданного закона алгебры логики

Задачи: 

  •  изучить литературу по логическим функциям, законам алгебры логики и таблицам истинности;
  •  разработать программу на языке программирования;
  •  подготовить отчет;

Для написания дипломной работы использовались учебник Н.Д.Угриновича «Информатика и ИКТ» 10 класс профильный уровень,  справочник В.Ю. Лысковой, Е.А. Ракитиной «логика в информатике» и том «Информатика» энциклопедии для детей Аванта+, которые излагают информацию по теме «алгебра логики» и предлагают развернутый материал. Также использовался справочник по программированию на языке Delphi – «Delphi. Быстрый старт»

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

Глава 1. Алгебра логики.

§1.1 Понятие алгебры логики. Основные логические операции.

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

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

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

Логическое отрицание (инверсия) – это высказывание с присоединенной частицей «не», в языках программирования, обозначающаяся not, в алгебре логики -  ̚А. Операция логического отрицания выражения с аргументом А записывается формулой:  ̚А. Значение логической операции определяется с помощью таблицы истинности (1). Так как эта логическая операция отрицания, то значение логического выражения является противоположным значению аргумента А.

А

̚А

0

1

1

0

Таблица 1. Таблица истинности логического отрицания

Логическое умножение (конъюнкция) – это объединение нескольких высказываний в одно логическое выражение с помощью союза «и» в естественных языках. В языках программирования эта логическая операция обозначается and, а в алгебре логики обозначается значком & («амперсенд»). Операция конъюнкции записывается формулой А & В, где А и В – это логические переменные, обозначающие какое-либо утверждение. Значение, т.е. истинность, этого выражения определяется с помощью таблицы истинности (2). Логическое умножение – строгая функция, поэтому результатом выполнения операции является «истина» только тогда, когда все аргументы принимают значения «истина». То есть высказывание будет верно, когда одновременно выполняются события А и В.

А

В

А & B

0

0

0

0

1

0

1

0

0

1

1

1

Таблица 2. Таблица истинности логического умножения

Логическое сложение (дизъюнкция) – это объединение нескольких высказываний в одно логическое выражение с помощью союза «или» в естественных языках.  В языках программирования эта логическая операция обозначается or, а в алгебре логики обозначается значком ˅. Операция логического сложения с логическими переменными А и В записывается формулой: А ˅ В. Значение этой логической операции определяется таблицей истинности (3). Логическое сложение – нестрогая функция, поэтому результатом выполнения операции является «истина», когда хотя бы один аргумент принимает значение «истина». То есть высказывание будет верно, когда выполняется хотя бы одно событие, обозначенное логическими переменными  А и В.

А

В

А ˅ B

0

0

0

0

1

1

1

0

1

1

1

1

Таблица 3. Таблица истинности логического сложения.

Операция строгой дизъюнкции (исключающая «или») – это объединение нескольких высказываний с помощью оборота речи «либо … , либо …». Операция строгой дизъюнкции подразумевает, что выполняется либо только событие А, либо только событие В. Обозначается эта операция А xor В. Значение этой логической операции определяется таблицей истинности (4), из которой видно, что высказывание будет истинно только тогда, когда только одно значение аргумента будет принимать значение «истина»:

А

В

А xor B

0

0

0

0

1

1

1

0

1

1

1

0

Таблица 4. Таблица истинности строгой дизъюнкции.

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

Логическое следование (импликация) – это высказывание, которое образуется соединением двух высказываний в одно, с помощью оборота речи «если … , то … » в естественных языках. Операция импликации в алгебре логики обозначается А → В. Про эту логическую операцию говорят: если А, то В; А имплицирует В; А влечет В; В следует из А.2 . Значение логической операции определяется с помощью таблицы истинности (5).

А

В

А → В

0

0

1

0

1

1

1

0

0

1

1

1

Таблица 5. Таблица истинности логического следования

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

В компьютере и в языках программирования операция импликации может быть заменена формулой:  ̚А ˅ В. Убедиться, что данные формулы тождественно равны, поможет таблица истинности. Построим таблицу истинности для этой формулы:

А

В

̚А

̚А ˅ В

0

0

1

1

0

1

1

1

1

0

0

0

1

1

0

1

Таблица 6.

При сравнении значений таблицы истинности логического следования (5) и таблицей истинности (6) для формулы  ̚А ˅ В,   видно, что при одинаковых наборах переменных результат выполнения логического выражения одинаков, следовательно, операцию импликации тождественно заменяет формула:  ̚А ˅ В.

Логическое равенство (эквивалентность) – это высказывание, которое образуется соединением двух высказываний в одно при помощи оборота речи «… тогда и только тогда, когда …»3 в естественных языках, а в алгебре логики обозначается А‹═› В и говорят, что А эквивалентно В. Истинность данной логической функции определяется с помощью таблицы истинности (7):

А

В

А ‹═›В

0

0

1

0

1

0

1

0

0

1

1

1

Таблица 7. Таблица истинности логического равенства.

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

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

(А&В) ˅ (̚А&̚B);

(А˅̚B)&(̚А˅В).

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

А

В

̚̚А

̚В

(̚А&̚B)

(А&В)

(А&В) ˅ (̚А&̚B)

0

0

1

1

1

0

1

0

1

1

0

0

0

0

1

0

0

1

0

0

0

1

1

0

0

0

1

1

Таблица 8.

Теперь построим таблицу истинности для второй формулы:

А

В

̚̚А

̚В

(А˅̚B)

(̚А˅В).

(А˅̚B)&(̚А˅В)

0

0

1

1

1

1

1

0

1

1

0

0

1

0

1

0

0

1

1

0

0

1

1

0

0

1

1

1

Таблица 9.

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

(А&В) ˅ (̚А&̚B);

(А˅̚B)&(̚А˅В).

§1.2. Логические выражения. Таблицы истинности.

Из логических переменных формируются сложные (составные) высказывания, состоящие из некоторого числа одновременно проверяющихся простых высказываний и логических операций. Такое составное высказывание можно записать в виде формулы, т.е. логического выражения. Для правильного написания высказывания в виде логического выражения необходимо записать его, учитывая приоритет выполнения логических операций: инверсия, конъюнкция, дизъюнкция/исключающая «или», эквивалентность/импликация. С помощью скобок группируются простые высказывания для изменения указанного порядка выполнения. Истинность логических выражений определяет построенная таблица истинности. Для построения таблицы истинности существуют определенные правила:

1) Количество наборов значений аргументов логического выражения вычисляется по формуле 2n, где n – это количество логических переменных в данном логическом выражении, а 2 – это количество значений («истина», «ложь»);

2) Количество столбцов в таблице считается посредством сложения количества переменных, то есть простых высказываний, и количества логических операций;

3) В первых столбцах обычно пишутся простые переменные, а далее по одной операции в каждый столбец, следуя приоритету выполнения логических операций.

4) Так как в языках программирования такие таблицы истинности «строятся» с помощью циклов и вложенных циклов, которые перебирают значения переменных от 0 до 1, то в столбцах, которые отведены под начальный набор значений переменных, будут перебираться значения от 0 до 1.

Например, определим истинность высказывания А & ̚ В ˅ С по таблице истинности. По формуле 2n, количество строк в таблице, отведенных под набор значений, равно 8, а количество столбцов равно 6.

Первый столбец значений А составляет восемь строк, значений переменных только два: 0 и 1, поэтому делим 8 на 2, получаем 4. Сначала четыре строки заполняем нулями, а потом четыре - единицами. Для каждого значения переменной А, под которую отведено четыре строки, соответствует два значения переменной В, следовательно,  делим 4 на 2, получаем 2. Записываем сперва два нуля, а потом две единицы. Далее для каждого значения аргумента В существует два значения аргумента С. Делим 2 на 2, получаем 1 и записываем 0 и 1 в эти две строки.
Итак,  первой выполняется операция отрицания, затем конъюнкция и уже потом дизъюнкция.  Поэтому и столбцы тоже располагаются в такой последовательности.

Определяем истинность частей высказывания, постепенно подходя к определению истинности всего выражения. В результате всех преобразований и вычислений высказывание будет истинно при следующих наборов значений аргументов: 001, 011, 100, 101, 111.

А

В

С

̚ В

А & ̚ В

А & ̚ В ˅ С

0

0

0

1

0

0

0

0

1

1

0

1

0

1

0

0

0

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

1

1

1

1

1

0

0

0

0

1

1

1

0

0

1

Таблица 10.

§1.3. Алгебра логики в компьютерах.

Чтобы компьютер смог реализовать выполнение логических выражений, существуют специальные дискретные  преобразователи, которые получают входные сигналы, кодирующиеся 0 и 1 – исходные значения аргументов логических функций – и на выходе выдает новое значение цифрового сигнала – значение функции при заданном наборе аргументов.  Цифровой сигнал – это сигнал, который может принимать только одно из двух установленных значений.4 Такие преобразователи называются логическими элементами компьютера. Существует всего три логических элемента, которые выполняют три  базовые логические операции: конъюнкция, дизъюнкция, инверсия. В соответствие с логической операцией, логические элементы называются: конъюнктор, дизъюнктор и инвертор.  Логические элементы компьютера получают на входе значения аргументов в виде цифрового сигнала, который равен 1, если напряжение электрической цепи находится в пределах от 2,4В до 5В (высокий уровень цифрового сигнала), и равен 0, если напряжение цепи находится в пределах от 0В до 0,5В (низкий уровень цифрового сигнала).

Логический элемент «не» (инвертор) соответствует логическому отрицанию - инверсии, поэтому на выходе выдает значение сигнала, противоположное значению входного сигнала.

Обозначение инвертора:

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

Обозначение конъюнктора:


Логический элемент «или» (дизъюнктор) соответствует логическому сложению – дизъюнкции. На выходе выдает значение сигнала, равному сумме значений входных сигналов.  На выходе значение сигнала будет равно 1,  когда хотя бы одно значение входных сигналов равно 1.  

Обозначение дизъюнктора:

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

Рассмотрим пример функциональной схемы для логического выражения:

А & ̚ В ˅ С. Первой выполняется операция логического отрицания, второй – операция логического умножения, а третьей – операция логического сложения. В соответствии с приоритетом выполнения схема будет выглядеть  так:

Построим таблицу значений выходов:

А

В

С

Выход (1)

Выход (2)

Выход (3)

0

0

0

1

0

0

0

0

1

1

0

1

0

1

0

0

0

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

1

1

1

1

1

0

0

0

0

1

1

1

0

0

1

Таблица 11.

Выход (1) соответствует операции  ̚ В, выход (2) соответствует  операции А & ̚ В, а выход (3) – операции А & ̚ В ˅ С.  Заменив выходы в таблице результатом выполнения логических операций соответствующих элементов, получим таблицу истинности (10) для данного логического выражения. Таким образом, таблицы совпадают, поэтому  данному логическому выражению соответствует именно эта функциональная схема.

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

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

СПИСОК ЛИТЕРАТУРЫ

  1.  Delphi. Быстрый старт. – СПб.: БХВ-Петербург, 2003
  2.  Лыскова В.Ю., Ракитина Е.А. Логика в информатике – М.:Лаборатория Базовых Знаний, 2004
  3.  Угринович Н.Д. Информатика и ИКТ. Профильный уровень. – М.:БИНОМ.Лаборатория знаний, 2011
  4.  Энциклопедия для детей. Том 22. Информатика. Глав.ред. Е.А.Хлебалина, вед. науч. ред. А.Г.Леонов. – М.: Аванта+, 2003

1 Логика в информатике / В.Ю. Лыскова, Е.А. Ракитина; М.: Лаборатория Базовых Знаний, 2004. - 160с.:ил, с.22

2 Логика в информатике / В.Ю. Лыскова, Е.А. Ракитина; М.: Лаборатория Базовых Знаний, 2004. - 160с.:ил, с.31-32

3 Логика в информатике / В.Ю. Лыскова, Е.А. Ракитина; М.: Лаборатория Базовых Знаний, 2004. - 160с.:ил, с.33-34

4 Логика в информатике / В.Ю. Лыскова, Е.А. Ракитина; М.: Лаборатория Базовых Знаний, 2004. - 160с.:ил, с.98


 

А также другие работы, которые могут Вас заинтересовать

26513. Основные этапы социально-экономического развития Японии 32 KB
  в руках США. цель – подписание мирного договора сделанного в США и АНГ. договоры как сепаратные м у США и Я. тут же подписан договор безопасности м у Я и США.
26514. Основные этапы социально-экономического и политического развития Индии в 1950 – 2000 гг. 55 KB
  Существенным элементом внешней политики ИНК стали неприсоединение к военным блокам и стремление к консолидации молодых независимых государств. Критике подверглась позиция ИНК в социальных вопросах. В ИНК существовали различные группировки отражавшие несовпадающие интересы социальных слоев связанных с этой партией от крупных капиталистов и землевладельцев до интеллигенции мелкой буржуазии города и деревни трудящихся масс. В этом многообразии коренились и сила общенациональный авторитет ИНК и его внутренняя слабость.
26515. Валютный рынок Украины 34.05 KB
  В сфере валютной политики Национальный банк ставит задачу иметь реальный курс украинской гривны относительно свободно конвертируемых валют на уровне сбалансированности спроса и предложения. Для решения этой задачи и упорядочения ситуации на валютном рынке
26516. Основные направления отечественной и зарубежной историографии 43.5 KB
  Барг, Лавровский: уникальная особенность Англии в том, что она является ед. в Европе страной где развитие буржуазных отношений происходило одновременно в городе и деревне. Именно в деревне кап. Отношения развились более глубоко, именно из деревни шел импульс. Центр тяжести АБР лежал в деревне.
26517. Аграрный вопрос в Великой английской и Великой французской революциях 38.5 KB
  До революции в английской деревни было 2 формы собственности: крестьянская копигольд и буржуазнодворянская рыцарское держание. Революции лекция – феодализма ко времени ВФР уже не было. Эта идея поддержана целым течением яркий представитель Фюре – феодализм как таковой во Франции исчез до революции. необходимости в революции не было.
26518. Основные проблемы и особенности войны северо-американских колоний Англии за независимость и образование США 45.5 KB
  Северовосточные колонии новая Англия – территории с ранним развитием ремесел мануфактуры судостроение и судоходство рыболовство. Это колонии которые пошли по буржуазному пути. Среднеатлантические колонии. Южные колонии плантации основанные на труде рабов.
26519. Дискуссии в отечественной и зарубежной историографии о периодизации ВФ буржуазной революции, ее характере, движущих силах и итогах 44 KB
  Ленин развил мысли Маркса и Энгельса; показал решающую роль крестьянства и плебейского элемента городов в победе революции высоко оценил роль якобинцев и диктатуры. революции роль перешла к историкам радикального направления. атлантической революции.