1. 2 Теоретические основы информатики Представление информации в компьютере




Скачать 316.88 Kb.
Название1. 2 Теоретические основы информатики Представление информации в компьютере
страница2/2
Дата публикации07.04.2014
Размер316.88 Kb.
ТипДокументы
zadocs.ru > Информатика > Документы
1   2
^

1.2.3 Элементы алгебры логики



1.2.3.1 Основные понятия
Алгебра логики или булева алгебра (ее разработчик – Дж. Буль) вытекает из логики, основу которой составили труды Аристотеля (384-322 гг до н. э.). Логика – наука о доказательных рассуждениях Правильность рассуждения определяется только его логической конструкцией (структурой), и не зависит конкретного содержания входящих в него рассуждений.

Математическая логика была создана во второй половине 19-го века, исчисления позволяют устранять неясности естественного языка. Математическая логика = Формальная логика + алгебраические операции.

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

В алгебре логике все переменные и функции могут принимать только два значения 0 (Ложь, False) и 1 (истина, True).

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

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

  • простое высказывание – повествовательное предложение, принимающее одно из двух возможных значений – истина или ложь;

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

  • рассуждение – цепочка взаимосвязанных фактов и умозаключений, вытекающих друг из друга;

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


^ 1.2.3.2 Операции (высказывания) алгебры логики

Типы высказываний (основные операции алгебры логики):

  1. Конъюнкция – логическое умножение (результат соединения высказываний с помощью связки “и”) дает сложное высказывание, истинное только тогда, когда истинны оба составляющие его высказывания обозначаются: xy или x & y или ху, читается “х и у”.

Обозначается Таблица истинности

на схемах & логического умножения


X

Y

Х  Y

0

0

0

1

0

0

0

1

0

1

1

1



  1. Дизъюнкция – логическое сложение (результат соединения высказываний с помощью связки ”или”) дает сложное высказывание, истинное, когда истинно хотя бы одно из составляющих его высказываний. Обозначается xy или x + y – дизъюнкция, читается “х или у”

Обозначается Таблица истинности

на схемах 1 логического сложения


X

Y

Х  Y

0

0

0

1

0

1

0

1

1

1

1

1




  1. Строгая дизъюнкция (результат соединения высказываний с помощью связки “исключающее или”) дает сложное высказывание, истинное, когда истинно только одно из составляющих его высказываний (xy или xy - строгая дизъюнкция).

Таблица истинности


X

Y

Х Y

0

0

0

0

1

1

1

0

1

1

1

0


Иначе эта операция называется “сложение по модулю 2”, т.к. при сложении четного количества единиц результат будет 0, а при сложении нечетного количества единиц – 1.

  1. Инверсия - логическое отрицание (результат применения к высказыванию связки “не”) дает сложное высказывание, истинное, когда исходное высказывание ложно (x или - инверсия).

^ Обозначается инверсия Таблица истинности инверсии


Х



0

1

1

0
на схемах



  1. Импликация (следование) (результат соединения высказываний с помощью связки “если ... , то”) дает сложное высказывание, ложное, только когда первое из составляющих его высказываний истинно, а второе - ложно (xy - импликация).

Таблица истинности

импликации

Х

Y

XY

0

0

1

0

1

1

1

0

0

1

1

1

  1. Эквиваленция (результат соединения высказываний с помощью связки “тогда и только тогда”) дает сложное высказывание, истинное, когда истинность составляющих его высказываний совпадает (X  Y или X  Y - эквиваленция).

Эта операция называется также “эквивалентность” или равнозначность. Ее таблица истинности

Х

Y

XY

0

0

1

0

1

0

1

0

0

1

1

1


Алгебра логики вводит аксиомы и основные законы, с помощью которых можно упростить схемную реализацию компьютерных устройств или алгоритмов обработки информации, тем самым повысить надежность и сократить затраты на обработку информации. Используются также логические операторы - кванторы общности (“для всех”) и существования (“существует”). Для сложных высказываний строятся таблицы истинности, например:

A

B

AB

AB

AB

0 (ЛОЖЬ)

0 (ЛОЖЬ)

0 (ЛОЖЬ)

0 (ЛОЖЬ)

1 (ИСТИНА)

0 (ЛОЖЬ)

1 (ИСТИНА)

0 (ЛОЖЬ)

1 (ИСТИНА)

1 (ИСТИНА)

1 (ИСТИНА)

0 (ЛОЖЬ)

0 (ЛОЖЬ)

1 (ИСТИНА)

0 (ЛОЖЬ)

1 (ИСТИНА)

1 (ИСТИНА)

1 (ИСТИНА)

1 (ИСТИНА)

1 (ИСТИНА)



^

1.2.3.3 Аксиомы алгебры логики

1. Закон одинарных элементов (конъюнкции и дизъюнкции)


1 + X = 1

0 + X = 0

Х + X = 1

Х  X = X.

2. Законы отрицания

  1. ^

    Закон дополнительных элементов





  1. ^

     Двойное отрицание








  1. ^

     Закон отрицательной логики (законы де Моргана):





^

3. Комбинационные законы.

  1. Закон тавтологии (многократное повторение)


X+X+X+X=X

X*X*X*X=X
  1.  Закон переместительный (коммутативности)


A+B = B+А

А  В = В  А
  1. ^

     Закон сочетательный (ассоциативности)


A+B+C= A+(B+C)

А  В  С = А  (В  С).
  1.  Закон распределительный (диструктивности)


A  (B+C) = А  В + А  С;

A + (BC) = (А + В)  (А + С).

^

4. Правило поглощения (одна переменная поглощает другие)


A + А  В = А;

A  (А + В) = А

5. Правило склеивания (выполняется только по одной переменной)




1.2.3.4 Приоритет операций в алгебре логике

В алгебре логики имеется старшинство операций:

  1. Действие в скобках

  2. Операция с одним операндом (одноместная операция) – НЕ

  3. Конъюнкция - И

  4. Дизъюнкция - ИЛИ

  5. Сумма по модулю 2.

Операции одного ранга выполняются слева направо в порядке написания логического выражения. Алгебра логики линейна и для неё справедлив принцип суперпозиции.
1   2

Похожие:

1. 2 Теоретические основы информатики Представление информации в компьютере icon1. Дискретное представление информации: кодирование цветного изображения...
Дискретное представление информации: кодирование цветного изображения в компьютере (растровый подход). Представление и обработка...

1. 2 Теоретические основы информатики Представление информации в компьютере icon1. Информация, ее виды. Свойства информации. Способы передачи информации....
...

1. 2 Теоретические основы информатики Представление информации в компьютере icon1. Информация, ее виды. Свойства информации. Способы передачи информации....
Применительно к компьютерной обработке данных под информацией понимают некоторую последовательность символических обозначений, несущую...

1. 2 Теоретические основы информатики Представление информации в компьютере iconСообщения, данные, сигнал, атрибутивные свойства информации, показатели...
Эволюция понятия «информация» в XIX и начале XX веков. Выдающиеся ученые информатики. История методов обработки информации в работах...

1. 2 Теоретические основы информатики Представление информации в компьютере iconТеоретические основы
Теоретические основы информационно-измерительной техники; рабочая программа. Методические указания. Контрольные задания для студ...

1. 2 Теоретические основы информатики Представление информации в компьютере icon1 Теоретические основы защиты документированной электронной информации...
Задачи, направления и основные мероприятия по защите электронной информации от несанкционированного доступа

1. 2 Теоретические основы информатики Представление информации в компьютере iconВопросы к зачету
...

1. 2 Теоретические основы информатики Представление информации в компьютере iconМинистерство внутренних дел РФ московский университет
...

1. 2 Теоретические основы информатики Представление информации в компьютере iconТеоретические вопросы: Понятие информации, свойства информации
Кодирование числовой информации в ЭВМ. Двоичный, восьмеричный и шестнадцатеричный коды

1. 2 Теоретические основы информатики Представление информации в компьютере iconПрограмма зачёта по дисциплине «Информатика»
Предмет информатики. Задачи информатики. Структура информатики. Основные понятия информатики

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов