Базовая логика

• Logic gates
  • Законы де Моргана: Позволяют упрощать и инвертировать сложные условия
  • AND
  • OR
  • XOR
  • NOT
  • NAND
  • NOR
  • XNOR
• Always ON
• Second tick
• XOR элемент
• OR gate with 3 inputs
• AND gate with 3 inputs

Logic gates

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

Логические вентили с помощью реле (www.falstad.com/circuit)

Логические вентили на современной логике CMOS: MOSFET (P-MOSFET/P-MOS и N-MOSFET/N-MOS)

P-MOS транзисторы используются в качестве подтягивающих резисторов, а N-MOS транзисторы — в качестве понижающих. Благодаря этому статическое энергопотребление логических элементов и схем на основе КМОП-технологии очень низкое по сравнению с логическими элементами, разработанными с использованием только N-MOS или только P-MOS транзисторов

P-MOS и N-MOS получают одинаковые управляющие сигналы, но работают инверсно

Именно эта комплементарность (Complementary) дала название CMOS — Complementary MOS.

N-MOSFET:

• Открывается при HIGH (1) на Gate (GND проходит на Drain)
• Закрывается при LOW (0) на Gate
• Хорошо проводит 0V (GND)
• Плохо проводит Vdd (потери Vth)
• Body (подложка) подключается к GND

P-MOSFET:

• Открывается при LOW (0) на Gate (Source проходит на Drain)
• Закрывается при HIGH (1) на Gate
• Хорошо проводит Vdd (+5V)
• Плохо проводит GND (потери Vth)
• Body подключается к Vdd

Body всегда к своему питанию (P-MOS к Vdd, N-MOS к GND)

В общем случае, любой логический элемент на основе КМОП-технологии состоит из повышающей и понижающей цепей. Повышающая цепь состоит из PMOS-транзисторов, а понижающая — из NMOS-транзисторов. Входы обеих цепей одинаковы.

Принцип работы КМОП-инвертора:

Когда входной сигнал логический «0», PMOS-транзистор будет включен, а NMOS-транзистор — выключен. Поэтому выход будет подключен к 5 В. Более того, поскольку PMOS-транзистор пропускает сильную логическую «1», выходное напряжение будет очень близко к напряжению питания.

С другой стороны, когда Vin равен логической «1», PMOS-транзистор будет выключен, а NMOS-транзистор — включен. В этом случае NMOS-транзистор понизит выходное напряжение до логического «0». А поскольку NMOS-транзистор пропускает сильный «0», выходное напряжение будет очень близко к 0 В.

Таким образом, в любой момент времени либо PMOS-транзистор включен, либо NMOS-транзистор включен. И нет прямого пути от источника питания к земле. И поэтому статическое энергопотребление логического элемента CMOS практически пренебрежимо мало.

Законы де Моргана: Позволяют упрощать и инвертировать сложные условия.

Исходное тождество !(A && B) эквивалентно ≡ !A || !B

• Если теперь отрицать обе части, получим:
  • !(!(A && B)) ≡ !(!A || !B)
  • убираем двойное отрицание слева, получим:
  • A && B ≡ !(!A || !B)

Исходное тождество !(A || B) ≡ !A && !B

• Если теперь отрицать обе части, получим:
  • A || B ≡ !(!A && !B)

AND — A && B

AND в логике и программировании означает И (логическое умножение или конъюнкция). Это логическая операция, которая выдает истину (True), только если оба операнда истинны. Если хотя бы один из операндов ложен, то результат — ложь. Так же объединение NAND + NOT эквивалентно AND.

• AND можно получить через NAND A && B ≡ !(A NAND B)
• AND можно получить через NOR A && B ≡ !(!A || !B) ≡ (A NOR A) NOR (B NOR B)

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}

fn or(a: u8, b: u8) -> u8 { a | b }
fn not(x: u8) -> u8 {!x & 1}

fn and(a: u8, b: u8) -> u8 {
    a & b
}

fn and_by_using_or(a: u8, b: u8) ->u8{
    not(or(not(a),not(b)))
}

fn main() {
    print_truth_table("AND", and);

    print_truth_table("AND", and_by_using_or);
}

OR — A || B

OR это логическая операция, которая выдает истину (True), если хотя бы один из операндов истинен. Мат. синтаксис A + B

• OR можно получить через AND (A || B) ≡ !(!A && !B)
• OR можно получить через NAND (A || B) ≡ (A NAND A) NAND (B NAND B)
• OR можно получить через NOR (A || B) ≡ !(!(A || B))

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}
fn and(a: u8, b: u8) -> u8 { a & b }
fn nand(a: u8, b: u8) -> u8 { not(a & b)}
fn not(x: u8) -> u8 { !x & 1 }

fn or(a: u8, b: u8) -> u8 {
    a | b
}
 
fn or_by_using_and(a: u8, b: u8) -> u8 { 
    not(and(not(a),not(b)))
}

fn or_by_using_nand(a: u8, b: u8) -> u8 { 
    nand(nand(a, a), nand(b, b))
}

fn main() {
    print_truth_table("OR", or);
    print_truth_table("OR", or_by_using_and);    
    print_truth_table("OR", or_by_using_nand);
}

XOR — A XOR B

XOR (от англ. Exclusive OR/Исключающее ИЛИ). Это логическая операция, которая выдает истину (True), если только один из операндов истинен, и ложь (False), если оба операнда одинаковы (оба истинны или оба ложны). Математически записывается как A ⊕ B

• XOR можно получить через AND + OR + NOT: A XOR B = (A && !B) || (!A && B)
• XOR можно получить через NAND: A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B))
• XOR можно получить через NOR: A XOR B = (A NOR B) NOR ((A NOR A) NOR (B NOR B))
• XOR можно получить через NAND + AND + OR: A XOR B = (A NAND B) && (A || B)

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}

fn and(a: u8, b: u8) -> u8 { a & b }
fn or(a: u8, b: u8) -> u8 { a | b }
fn nand(a: u8, b: u8) -> u8 { 
  not(a & b)  
}
fn not(x: u8) -> u8 {!x & 1}

fn xor(a: u8, b: u8) -> u8 {
    a ^ b
}
 
fn xor_by_using_nand_and_or(a: u8, b: u8) -> u8 {
    and(nand(a, b), or(a, b))
}

fn main() {
    print_truth_table("XOR", xor);
    print_truth_table("XOR", xor_by_using_nand_and_or);    
}

NOT — !A

NOT (Инвертор) Инвертирует входное значение. Истина становится Ложью, и наоборот.

0 -> NOT -> 1

1 -> NOT -> 0

// Операция &1 означает нормализовать 8 бит к 0 или 1 
// т.е. оставить только младший бит, всё остальное выбросить
// Для типа bool нормализация не нужна
fn not(x: u8) -> u8 {
  !x & 1
}
 
fn main() {
    assert_eq!(not(1),0);
    assert_eq!(not(0),1);    
}

NAND — !(A && B)

NAND (Not-AND/И-НЕ) Противоположность AND. Выдает Ложь, только если оба входа Истинны. Т.е. сперва применяется операция AND и к результату ее применяется операция NOT: 1 AND 1 = 1 NOT = 0

Из AND можно получить NAND и наоборот:

• NAND можно получить через AND, так как A && B ≡ !(A NAND B)
• NAND можно получить через OR !(A && B) ≡ (!A) || (!B)
• NAND можно получить через NOR !(A && B) ≡ (A NOR A) OR (B NOR B)

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}

fn and(a: u8, b: u8) -> u8 { a & b }
fn or(a: u8, b: u8) -> u8 { a | b }
fn nor(a: u8, b: u8) -> u8 { not(a | b) }
fn not(x: u8) -> u8 {!x & 1}

fn nand(a: u8, b: u8) -> u8 { 
  not((a & b)) 
}

fn nand_by_using_and(a: u8, b: u8) -> u8 { 
  not(and(a, b))
}

fn nand_by_using_or(a: u8, b: u8) -> u8 { 
  or(not(a), not(b))  
}

fn nand_by_using_nor(a: u8, b: u8) -> u8 { 
  or(nor(a, a), nor(b, b)) 
}

fn main() {
    print_truth_table("NAND", nand);
    print_truth_table("NAND", nand_by_using_and);
    print_truth_table("NAND", nand_by_using_or);
    print_truth_table("NAND", nand_by_using_nor);
}

NOR — !(A || B)

NOR (Not-OR/ИЛИ-НЕ) Противоположность OR. Выдает Истину, только если оба входа Ложны. Т.е. сперва применяется операция OR и к результату ее применяется операция NOT: 0 OR 0 = 0 NOT = 1 Так же можно получить NOR

• NOR можно получить через AND !(A || B) ≡ (! A) && (! B)
• NOR можно получить через NAND !(A || B) ≡ (! A) && (! B) = !(!A NAND !B)

Так же можно получить NOR если инвертировать выход OR, сравните таблицу истинности, если выход NOR !(A || B) инвертировать то получим OR A || B

Задача: вывести NOR !(A || B) имея только NAND !(A && B) и NOT !A

• по закону де Моргана
  • A || B ≡ !(!A && !B)
• тогда через его отрицание получим NOR
  • !(A || B) ≡ !(!(!A && !B))
• устраним двойное отрицание
  • !(A || B) ≡ !A && !B
• преобразуем AND в NAND
  • !(A || B) ≡ !(!A NAND !B)

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}

fn and(a: u8, b: u8) -> u8 { a & b }
fn not(x: u8) -> u8 {!x & 1}

fn nor(a: u8, b: u8) -> u8 {
    not(a | b)
}

fn nor_by_using_and(a: u8, b: u8) -> u8 { 
    and(not(a), not(b))  
}

fn main() {
    print_truth_table("NOR", nor);
    print_truth_table("NOR", nor_by_using_and);    
 
}

XNOR — !(A ⊕ B)

XNOR (Exclusive-NOR/Исключающее ИЛИ-НЕ/NOT XOR). Противоположность XOR. Выдает Истину, если оба входа одинаковы (оба Ложны или оба Истинны).

• XNOR можно получить через XOR + NOT: !(A ⊕ B) = !(A XOR B)
• XNOR можно получить через AND + OR + NOT: !(A ⊕ B) = (A && B) || (!A && !B)
• XNOR можно получить через XOR + NAND: !(A ⊕ B) = XOR NAND XOR
• XNOR можно получить через NOR: !(A ⊕ B) = ((A NOR B) NOR ((A NOR A) NOR (B NOR B))) NOR ((A NOR B) NOR ((A NOR A) NOR (B NOR B)))

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}

fn not(x: u8) -> u8 {!x & 1}
fn xor(a: u8, b: u8) -> u8 { a ^ b}

fn xnor(a: u8, b: u8) -> u8 {
    not(xor(a,b))  
}

fn main() {
    print_truth_table("XNOR", xnor);
}

Always ON

(Всегда включен)

Задача: Как получать на выходе всегда 1 при любом входе, имея в расспоряжении NOR, NAND, AND, OR, NOT

Один из вариантов, к результату NOR применить OR, так как их таблицы истинности наглядно показывают это поведение. Тогда мы сможем все нули NOR преобразовать в 1 через OR.

Second tick

Второй тик

Задача: Ожидаемый выход 1 только при входе A=1, B=0

... решение напоминает таблицу истинности для XOR

если для случая A=0, B=1 инвертировать результат через AND то можно получить трубуемое поведение.

Но более простой вариант это NOT + AND. Если мы вход B предварительно инвертируем, то при случаии A=1, B=0 мы инвертируем B и получим 1, а в остальных случаях результат через AND всегда будет 0

Ожидаемое поведение, таблица истинности:

A   0 1 0 1
B   0 0 1 1
out 0 1 0 0

const NAME_WIDTH: usize = 4;
fn print_truth_table(name: &str, gate: fn(u8, u8) -> u8) {
    println!("|{:^width$}| 0 | 1 |", name, width = NAME_WIDTH);
    println!("|{:-^width$}|---|---|", "", width = NAME_WIDTH);

    for b in 0..=1 {
       println!(
           "|{:^width$}| {} | {} |",
           b,
           gate(0, b),
           gate(1, b),
           width = NAME_WIDTH
       );
    }
    println!("");
}
fn and(a: u8, b: u8) -> u8 { a & b }
fn not(x: u8) -> u8 {!x & 1}

fn tick(a: u8, b: u8) -> u8 { 
    and(a, not(b))
}

fn main() {
    print_truth_table("tick", tick);
}

XOR элемент

Задача: Получить XOR

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

OR gate with 3 inputs

(A || B) || (B || C)

AND gate with 3 inputs

(A && B) && (B && C)