Экзаменационные вопросы по курсу математической логики

Экзаменационные вопросы по курсу математической логики

1) Высказывание и высказывательные формы. Элементарные и составные предложения. Конъюнкция и дизъюнкция. Отрицание. Импликация и эквиваленция

Высказывание - повествовательное предложение, которое либо истинно, либо ложно. Пример: Ленинград расположен на Неве.

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

Пример: Функция F - периодична.

Логика высказывания решает вопрос об истинности высказывания.

Составное предложение отличается от простого тем, что в нем представлено несколько высказываний.

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

Логические операции

 

1) Отрицание (неверно, что)

A - высказывание

 - неверно, что A

2) Логическое умножение (и - and) - конъюнкция (<>)

Конъюнкция истина тогда и только тогда, когда истины оба высказывания (справедливо для n истинных высказываний).

3) Логическое сложение (или - or) - дизъюнкция (<>)

4) Импликация (если:, то:) - (<>)

, где

А - антецедент

B - консеквент

Из истины не может следовать ложь.

5) Эквиваленция (тогда и только тогда) - (<>)

Таблица истинности для всех логических операций:

 2) Формулы логики высказывания. Язык и метаязык. Составление таблиц истинности для данных формул. Тавтология

Формулы логики высказывания:

- истина (И) и ложь (Л) - const;

- x, y, z (x1, x2:) - переменные;

- если F - формула, то  - также формула;

- если F1 и F2 - формулы, то , , ,  - тоже формулы.

Формализовать - значит:

1) Каждому простому предложению сопоставить элементарную формулу.

2) Если предложение составное, то выделяем простые предложения, заменяем их на элементарные формулы, вместо связок расставляем знаки логических операций.

3) Если нужно, расставляем круглые скобки.

Язык-объект - тот, который изучают.

Метаязык - язык, с помощью которого изучают.

Пример: pascal - язык-объект, русский язык - метаязык.

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

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

Если в формулу входит n переменных, то формула будет иметь 2n наборов значений.

Составление таблиц истинности для данных формул

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

Пример:

В данном случае F - тавтология.

3) Равносильность формул логики высказывания. Законы логики. Выражение импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание

Формула F1 равносильна формуле F2, если при любых наборах входящих в них переменных формулы принимают одинаковые значение истинности.

Формула F1 равносильна формуле F2 , если их эквиваленция есть тавтология, или , если  - тавтология.

Свойства равносильности:

1) Рефлексивность ()

2) Симметричность (Если , то )

3) Транзитивность ()

Законы логики:

1)  - тождествия

2)  - противоречия

3)  - исключенного третьего

4)  - двойного отрицания

5)  - идемпотентности

6)  - коммутативности

7)  - ассоциативности

8)  - дистрибутивности

9)  - де Моргана

10)

11)  - поглощения

12)  - склеивания

Выражение импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание

4) Равносильные преобразования. Упрощение формул. Выражение импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание

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

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

Выражение импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание

5) Обратные предложения. Противоположные предложения. Достаточные и необходимые условия

Прямые обратные и противоположные предложения:

 - прямое предложение

 - обратное предложение

 - противоположное предложение

 - обратно противоположное предложение

Пример:

1) если треугольник равнобедренный, то углы при основании равны

2) если углы при основании равны, то треугольник равнобедренный

3) если треугольник не равнобедренный, то его углы при основании не равны

4) если углы при основании не равны, то треугольник не равнобедренный

Достаточные и необходимые условия

В теореме  A - достаточное условие, B - необходимое (если четырёхугольник ромб, то его диагонали перпендикулярны).

Условие A является достаточным, чтобы выполнить условие, B является необходимым, но не достаточным. Если существуют прямая и обратная теоремы, то A и B - достаточные и необходимые условия.

6) Закон контрапозиции. Достаточные и необходимые условия

Закон контрапозиции: прямое предложение равносильно обратно противоположному.

Наглядно это демонстрирует таблица истинности

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

Пример: если m2 - нечётно, то m - нечётно => если m - чётно, то m2 - чётно

Достаточные и необходимые условия

В теореме  A - достаточное условие, B - необходимое (если четырёхугольник ромб, то его диагонали перпендикулярны).

Условие A является достаточным, чтобы выполнить условие, B является необходимым, но не достаточным. Если существуют прямая и обратная теоремы, то A и B - достаточные и необходимые условия.

7) Отношение следования между формулами логики высказываний. Правильные и неправильные аргументы

Формула F2 следует из формулы F1, если их импликация есть тавтология, или F1 => F2, если F1F2 - тавтология.

Формула F2 следует из формулы F1, если не найдено такого набора значений, при которых F1 - истина, F2 - ложь.

Свойства следования:

1) Рефлексивность (F => F)

2) Транзитивность ()

Определить следует ли одна формула из другой можно с помощью:

1) равносильных преобразований, составив импликацию двух формул и упростив эту импликацию.

2) составления таблицы истинности для импликации двух формул и проверки, является ли эта импликация тавтологией.

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

Изначально предполагается, что все посылки истинны => их конъюнкция истинна. Заключение должно быть истинным.

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

Для проверки правильности аргумента нужно составить конъюнкцию формализованных посылок и проверить, следует ли из конъюнкции заключение.

Способы проверки:

- таблица истинности;

- упрощение;

- сокращённый метод;

- привести к стандартному виду аргумент.

Стандартные виды аргументов:


Правильные аргументы:

               


Неправильные аргументы:

              


8) Сокращённые способ проверки аргументов

Сокращённый метод проверки аргументов заключается в том, что:

1) Делается предположение, что все посылки истинны, а следствие - ложно, т. е. единственный вариант, когда аргумент неверен

2) Затем мы проводим ряд рассуждений

3) И в наших рассуждениях есть противоречия, то наше предположение неверно => аргумент правильный, если же противоречий нет, то посылки истинны, а следствие ложно => аргумент неправильный.

Главная задача этого метода - определить такой набор переменных, при котором аргумент будет неверен или доказать, что их нет.

Пример:

Последовательное рассуждение:

1) Если заключение  - ложно, то У и П - ложны => записываем их в правую колонку

2) Т. к. конъюнкция посылок истинна, то каждая посылка - истинна

3) Из условий (1) и (2) делаем выводы: чтобы  и  были истинны, необходимо, чтобы К и Л были ложны.

4) Из условия (3) следует, что третья посылка будет ложна

Итак, мы получили противоречие условию (2) => аргумент правильный. В ответе следует записать, что <аргумент истинный>.

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

9) Составление формул по заданным таблицам истинности. Нормальные формы. Приведений формул к совершенным нормальным формам с помощью равносильных преобразований

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

Существует два вида: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ).

КНФ:

ДНФ:

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

СКНФ:

СДНФ:

Правила построения СДНФ и СКНФ по таблице истинности

Составим таблицу истинности для формулы.

Из набора переменных, где формула истинна, сделаем их конъюнкцию (или их отрицаний), так чтобы она была истинной. А уже из всех полученных истинных конъюнкций составим одну дизъюнкцию - СДНФ.

Из набора переменных, где формула ложна, сделаем их дизъюнкцию (или их отрицаний), так чтобы она была ложной. Из всех дизъюнкций составим конъюнкцию - СКНФ.

Пример:

СКНФ:

СДНФ:

Правила приведения в СДНФ с помощью равносильных преобразований:

1) Приводим к нормальному виду

2) Из всех одинаковых членов дизъюнкции оставляем только один

3) Если в каком-то слагаемом не хватает переменной x0, то домножаем на

4) Раскрываем скобки

5) Смотри 2

Пример:

Правила приведения в СКНФ:

1) Приводим к нормальному виду

2) Из всех одинаковых членов конъюнкции оставляем только один

3) Если в каком-то слагаемом не хватает переменной x0, то прибавляем

4) Раскладываем на множители

5) Смотри 2

10) Получение следствий из данных посылок

Получение всех следствий из посылок

Допустим, есть несколько посылок. Какие возможны заключения их этих истинных посылок?

1) Составляем конъюнкцию всех посылок

2) Находим СКНФ

3) Выписываем из СКНФ все возможные варианты комбинаций сомножителей (2n - 1, где n - количество этих сомножителей)

Пример:

Возможные следствия:

1)  2)  3)  4)

5)  6)

7)

Доказательство, что любое из выражений является заключением

Все посылки истинны => их конъюнкция истинна => СКНФ - истинна, т. к. получаем равносильными преобразованиями => такое возможно, если истинны все сомножители => любой сомножитель (либо их комбинация) будет являться заключением.

Получение следствий, содержащих заданные переменные

1) Составляем таблицу истинности

2) Подчёркиваем строку, где одновременно истинны все посылки

3) Подчёркиваем значения заданных переменных в этих случаях

4) Составляем СДНФ по выделенным строкам, учитывая только заданные переменные

5) Упрощаем СДНФ

Пример:

11) Предикаты и способы их задания. Множество истинности предиката. Равносильность высказывательных форм.

Предикаты

Предикат - это функция, которая отображает множество объектов на множество <истина - ложь>.

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

(x) - высказывательная форма

P, Q, R - предикаты

Множество - неупорядоченная совокупность однотипных элементов.

Существует два способа задания предиката:

1) Высказывательной формой, т. е. следует задать высказывательную форму и множество объектов для переменных

(x) = <x - нечетное>, Mx = N

2) Табличный

Табличный способ применяется тогда, когда мало переменных (от 1 до 3), от которых зависит предикат и множество объектов, на котором задан данный предикат невелико.

N-местная высказывательная форма - высказывательная форма, зависящая от N переменных.

(x) = <x > 1>, Mx = R - одноместная высказывательная форма

(x, y, z) = x + y - z = 10, Mx = My = Mz = R - трехместная высказывательная форма

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

Если при каком-то значении переменной высказывательная форма, не имеющая знаков логических операций, теряет смысл, то её принято считать ложной.

(x) =  - истина при x < 0

(x) =  - ложь при x < 0

Упорядоченная n-ка - совокупность n не обязательно различных объектов вместе с заданным порядком их расположения.

{а; п; е; л; ь; с; и; н} = {с; п; а; н; и; е; л; ь} - для множества

(а; п; е; л; ь; с; и; н) ≠ (с; п; а; н; и; е; л; ь) - для упорядоченной n-ки

Декартово произведение (произведение n множеств) - такое множество упорядоченных n-ок, в которых на 1-ом месте объект из 1-ого множества, на 2-ом из 2-ого:

Пусть Mx = {a; b; c}, My = {1; 2}, тогда их декартово произведение равно:

Mx * My = {(a; 1); (b; 2); (a; 2); (c; 1); (c; 2); (b; 1)}

Множество истинности предикатов

 (<пэ с крышкой>) - множество истинности предикатов, множество тех значений x, при которых предикат принимает значение <истина>.

Если предикат зависит от двух переменных, то множеством истинности будет множество пар, в которых на 1-ом месте объект из Mx, на втором - из My.

Если (x, y) = <x > y>, Mx = {1; 2; 3), то  = {(3; 1); (3; 2); (2; 1)}

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

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

Равносильность высказывательных форм

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


Равносильные:

x + 1 = 0 <=> x = cos π

|x| > 3 <=> x2 - 90 > 0

|x| < 0 <=>  sin x = 2

x = 1 <=> x + y - y = 1


Неравносильные:

x > 0 <≠> y > 0

x = x <≠>  = x


Равносильное преобразование - замена высказывательной формы  на высказывательную форму  так, что значении истинности  при тех же наборах переменных сохраняется.

Свойства равносильности:

- рефлексивность;

- транзитивность;

- симметричность.

12) Логические операции и операции над множествами. Следование и включение.

Рассмотрим пять основных логических операций над множествами: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

1) Отрицание

P = (x)

Q =

 ( - закрашенная область на рисунке)


2) Конъюнкция

P1 = (x)

P2 = (x)

Q =

3) Дизъюнкция

P1 = (x)

P2 = (x)

Q =


4) Импликация

P1 = (x)

P2 = (x)

Q =

5) Эквиваленция

P1 = (x)

P2 = (x)

Q =


Следование и включение

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

 Включение одного множества в другое значит, что множество истинности одного меньше или равно множеству истинности второго, т. е. .

При обязательно выполняется  или

Таким образом, из тождественно ложной высказывательной формы (|x| < 0) следует любая высказывательная форма. А также тождественно истинная высказывательная форма (|x| ≥ 0) будет следовать из любой.

Пример:


Дано:

(x) = <x - кратно 3>

(x) = <x - четное>

Mx = {1; 3; 5; 6; 7; 9; 11; 12}


Итого:

(x)(x)


13) Свойства как одноместные предикаты. Классификация.

Свойства как одноместные предикаты

Рассмотрим высказывательную форму (x) = <у домашнего животного x четыре ноги>. Таким образом, одноместный предикат может рассматриваться как свойство объекта, т. е. объект может обладать данным свойством или нет.

Объемом данного свойства n - количество объектов из заданного множества, обладающих данным свойством.

Объем не всегда можно определить точно, т. к. он может быть бесконечным. Если множество истинности предиката пустое, то и объем свойства будет нулевым (n = 0).

Определим объём некоторых высказывательных форм (Mx = R):

(x) = <x ≥ 0>, n = ∞

(x) = <x2 - 1 = 0>, n = 2

(x) = <x - число букв в слове <уравнение>, n = 1

(x) = <x - число тупых углов в прямоугольном треугольнике>, n = 0

Классификация

Классификация - разбиение данного множества на классы (подмножества).

Если на заданном множестве М задаются n различных предикатов, то множество М при этом разбивается на  классов.

Рассмотрим классы при различном количестве предикатов:

n = 1:

n = 2:

n = 3:

Пример:

P(x) - <x - кратно 2>

Q(x) - <x - кратно 3>

R(x) - <x - кратно 5>

Mx = {1..20}

Правила правильной классификации:

- пересечение любых двух классов пусто.

- объединение всех классов дает исходное множество.

14) Отношения как многоместные предикаты. Свойства бинарных отношений.

Отношения

Бинарные отношения связывают два объекта, бывают: <, >, ║, ≤, ≥, ≠, ┴, =, <быть сверстниками>, родство, дружба, любовь, <жить в одном доме>, равносильность, следование:

xRy - объект x находится в отношении R с объектом y.

Свойства бинарных отношений:

1) Рефлексивность - xRx (= ,=> , ║, ≤, ≥, ≡, родство, любовь, <друг>)

2) Симметричность - (xRy)  (yRx)  (║, =, ┴, ≠, ≤, ≥, дружба, родство, <быть одноклассниками>, <быть тезками>)

3) Транзитивность - (xRy)  (yRz) => (xRz) (>, <, ≥, ≤, =, ║, кровное родство)

4) Антирефлексивность -  (<, >, ≠, ┴)

5) Антисимметричность - ((xRy)  (yRz)) => () (<, >, <жить этажом выше>)

6) Связанность - (xy) => ((xRy)  (yRx)) (>, <, ≤, ≥)

15) Отношения эквивалентности и отношения порядка.

Отношения эквиваленции - отношения, которые обладают свойствами симметричности, рефлективности и транзитивности.

(x,y) = <x и y - тезки>

(x,y) = <x и y - одноклассники>

Если на исходном множестве заданно какое-то отношение эквивалентности, то при этом исходное множество разбивается на классы эквивалентности. При этом любые два объекта одного класса попарно эквивалентны, а любые два объекта из разных классов не эквивалентны.

Отношения порядка - отношения, которые обладают свойствами транзитивности и антисимметричности.

Отношения порядка бывают:

- строгого порядка: + антирефлексивность;

- нестрогого порядка: + рефлексивность;

- совершенного порядка: + связанность.

16) Кванторы общности и существования

 - квантор общности, используется вместо слов: <для любого>, <для каждого>, <для всех>.

(x2 + y + 1 > 0) - <для всех x верно, что x2 + y + 1 > 0>

 - квантор существования, используется вместо слов: <существует>, <найдется>.

(5 + x =5) - <существует такое x, что 5 + x = 5>

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

17) Квантификация многоместной высказывательной формы.

Квантификация - переход от высказывательной формы к истинному высказыванию.

Рассмотрим двуместную высказывательную форму и всевозможные варианты её квантификации:


(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)


(1) ≡ (2)

(3) ≡ (4)

Одноименные кванторы можно менять местами

(6) => (5)

(8) => (7)


Если высказывательная форма зависит от n переменных, то при квантификации высказывательной формы по xi переменной, xi переменная становится связанной (связана квантором), при этом все остальные называются свободными.

Чтобы перейти от высказывательной формы  к истинному высказыванию нужно проквантифицировать её n раз по каждой переменной.

18) Отрицание предложений кванторами.

Рассмотрим такой пример:  (отрицание предложения необходимо начинать со слов <неверно, что:>) - <неверно, что все ученики отличники>. Попытаемся перефразировать: <среди учеников есть хотя бы неотличник> или , т. е.  ≡ . Ещё один пример:  ≡ .

Правила построения отрицания предложения с кванторами:

- каждый квантор меняем на противоположный;

- отрицание переносим на высказывательную форму.

Пример:

Предложение: <в каждой стране найдётся город, у всех жителей которого глаза одинакового цвета>.

Запись кванторами: (глаза одинакового цвета)

Отрицание кванторами: (неверно, что глаза одинакового цвета)

Отрицание предложение: <существует страна, в каждом городе которой найдётся житель с глазами разного цвета>.

19) Численные кванторы

а) Не менее n

б) Не более n

в) Ровно n

1) n = 1

a)  - кубическое уравнение имеет не менее одного корня.

б)  - две прямые пересекаются не более чем в одной точке

в)  - линейное уравнение имеет один корень

2) n = 2

а)  - в треугольнике находится не менее двух острых углов

б) - квадратное уравнение имеет не более двух действительных корней

в)  - в прямоугольном треугольнике ровно два острых угла.

Аналогичным образом можно сделать и для n = 3, 4 и так далее.

20) Символическая запись определений и теорем.

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

Пример: число A называется пределом числовой последовательности  тогда и только тогда, когда для любого E больше <0> существует такое число N, что для любого n, где n больше либо равно N, выполняется условие, что модуль разности числа A и любого числа последовательности меньше E.

21) Булевы функции и функционально полные наборы

Булевы функции

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

Логическая операция <отрицание конъюнкции> (<>) имеет другое обозначение и название - стрелка Пирса (<>), а логическая операция <отрицание дизъюнкции> (<>) - штрих Шеффера и обозначается (<|>). Называются они соответственно <и-не> и <или-не>.

Функционально полные наборы

Функционально полные наборы - наборы логических операций, с помощью которых можно выразить все остальные.

Например, такими наборами являются:

- конъюнкция, дизъюнкция, отрицание ();

- конъюнкция, отрицание ();

- дизъюнкция, отрицание ();

- штрих Шеффера ( | );

- стрелка Пирса ().

Выразим через эти наборы все основные операции (отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция)


1) Конъюнкция, дизъюнкция, отрицание


2) Конъюнкция, отрицание


3) Дизъюнкция, отрицание

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

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

22) Логические элементы и синтез комбинационных схем

Логические элементы

Логические элементы соответствуют определённым логическим операциям. Например, конъюнкции соответствует конъюнктор, дизъюнкции - дизъюнктор, отрицанию - инвертор:

Таким образом, например, можно составить логические элементы, соответствующие стрелке Пирса и штриху Шеффера:

Предположим, нам дан логический элемент, составленный из каких-то более простых логических элементов, у которого три входа X, Y и Z и один выход F. Нам необходимо составить его возможную схему строения:

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

На основе полученной таблицы мы составляем по нулям или единицам СКНФ или СДНФ соответственно (в зависимости от того, чего меньше). После чего стараемся её минимизировать, если это возможно:

СДНФ:

На основе такой формулы строим комбинационную схему:

Одноразрядный двоичный полусумматор

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

СДНФ:

СДНФ:

Таким образом, схема будет выглядеть так:

Полный одноразрядный двоичный сумматор

Составим также схему и полного одноразрядного двоичного сумматора. В отличие от полусумматора он учитывает и предыдущий разряд для вычисления текущего.

СДНФ:

СДНФ:

Пусть , тогда

Комбинационная схема:

23) Виды триггеров и двоичные счетчики

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

Рассмотрим один из самых простых триггеров - RS-триггер:

RS-триггер имеет два входа (R и S) и два выхода (T и Q).


Схема устройства:


Временная диаграмма:


Из диаграммы видно, что импульс выходит либо только на выходе T, либо на Q, т. е.  и , а на схемах RS-триггер будет выглядеть так:

Таким образом, RS-триггер запоминает, на какой элемент пришёл последний импульс.

Следующий вид триггера, более сложный, - D-триггер:

D-триггер имеет два входа (C и D) и два выхода (T и ).


Схема устройства:

Отметим, что R и S входы предназначены для <сброса> триггера, т. е. для обнуления.


Временная диаграмма:


На схемах D-триггер обозначается так:


Таким образом, D-триггер запоминает, что было на D, когда приходит импульс на C.

Ещё один тип триггеров - триггер со счётным входом:

Триггер со счётным входом имеет один вход (C) и два выхода (T и ).

Схема устройства:


R и S входы также предназначены для <сброса> триггера, т. е. для обнуления.


Временная диаграмма:


Обозначение на схемах:

Триггер со счётным входом меняет состояние (переворачивается), при каждом приходе импульса.

На схеме триггера со счётным входом использован элемент, который называется формирователем. Формирователь имеет один вход (in) и один выход (out).


Схема формирователя:


Временная диаграмма:


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

Двоичные счётчики

Рассмотрим пример двоичного счётчика (считает от 0 до 10), состоящего из нескольких триггеров со счётным входом.

Схема устройства:

Временная диаграмма:

На схеме отражено, что сброс счётчика осуществляется при тех значениях импульса на выходах T0, T1, T2, T3, которые соответствуют числу 10 в двоичной записи, т. е. 1010, когда T1 = 1 и T3 = 1, T0 = 0 и T2 = 0. Таблица значений счётчика будет выглядеть так:

 
Адрес страницы на сайте :
http://redpencil.ru/obschie-voprosi-po-mat.-logike/ekzamenatsionnie-voprosi-po-kursu-matematicheskoy-logiki.html

© RedPencil, 2018