82342

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

Дипломная

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

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

Русский

2015-02-27

155 KB

25 чел.

ГБОУ Гимназия № 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


 

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

27281. Туризм как многогранное явление 26 KB
  Туризм – как вид отдыха путешествия Туризм – как бизнес транспорт размещение питание развлечение торговые предпр экск бюро музеи турфирмы Туризм – как отрасль экономики Туризм – как рынок рынок потребителей спрос на турпродукт рынок производителейвысокая конкуренция появление новых видов услуг Турпродукт – комплекс услуг по перевозке и размещению оказываемых за общую цену по договору о реализации туристского продукта. Туризм – как общественное движение зона предпринимат распределений...
27282. Туристские макрорег мира 30.5 KB
  АзиатскоТихоокеанский Страны Восточной и ЮВ Азии Австралия и Океания 4.Африканский Страны Африки кроме Египта и Ливии 5. Исходя из экономических природных исторических и других предпосылок можно выделить 4 туристских территории: 1ВосточноЕвропейская зона: Польша Центральный Чехия Словакия Венгрия Причерноморский Румыния Болгария 2Зона Северной Европы Скандинавские страны Норвегия Швеция Финляндия Дания 3ЗападноЕвропейская зона Британский Великобритания Ирландия Альпийский Франция Швейцария Австрия...
27283. Факторы регионализма 25 KB
  К факторам регионализма можно отнести: 1.Этнический фактор Этнос исторически возникший вид социальной группировки людей который обладает совокупностью признаков.Демографический фактор демографиянаука которая изучает воспроизводство населения.
27284. Сегментирование. Целевой рынок 24 KB
  Целевой рынок Сегментация рынка заключается в делении рынка на четкие группы покупателей которым следует адресовать разные продукты и разные маркет усилия. Целевой рынок – совокупность сущ и потенц покупателей. Стратегия охвата целевого рынка: Недиффер маркет – товар рынок организация выходит на рынок с одним продуктомПр. Диффер маркет – товар1 рынок1 товар2 рынок2 деят организации на неск сегментахПр.
27286. Цикл обслуживания туриста 26 KB
  Обслуживание во время пребывания Основные услуги Орг прожив гостей питание услуги горничной выдача ключей на ресепшен. Дополнит услуги Услуги бизнесцентра пользование междунар междугор связью копир работы предоставл компьютера переводческие услуги услуги сервисбюро брон билетов орг экс обслуж орг питанияразл подраздел общепита обслуж в номерах орг банкетов орг хран личных вещей камера хранения депозитная ячейка платная эл инд сейфы телекоммуникац услугипобудка услуги платного ТВ анимац услуги Выезд и выписка...
27287. Экономика отрасли 27 KB
  Показатели качества: 1.Техничности это те показатели которые обеспечивают рациональность использования материалов. Экологические показатели отражают степень влияния вредных воздействий на окр. Показатели конкурентоспособности: 1.
27288. Экскурсионная деятельность 30.5 KB
  Методические приемы рассказа: прием экс. прием описания. прием характтикиопред. прием комментированияразъясняет смысл события или замысел автора.
27289. Маркет исследование 25 KB
  Маркет инф получается на основе первичных и вторичных данных. Первичные – получаются в результате спец провед маркет исслед для решения конкретной проблемы. источников для целей отличных от целей маркет исслед.