Two states. Propositional logic: "a formal system in which the formulas of a formal language may be interpreted as representing propositions". Truth-functional propositional logic: truth values of propositions limited to true and false.
Atomic propositions can be linked by logical connectives (AND, OR, NOT).
Truth tables: OR, AND, NOT, XOR, NAND, NOR. The out puts for these are: {0 1 1 1}, {0 0 0 1}, {invert}, {0 1 1 0}, {1 1 1 0}, {1 0 0 0}
| OR | AND | XOR |
| NOT | NOR | NAND |
Circuits with switches: parallel (OR); series (AND). Example: (X AND Y) OR (X AND Z): X.Y + X.Z: X(Y + Z). Extended expressions involving numerous operators can be analysed and simplified with Boolean algebra or shown to be equivalent with truth tables.
Used for design of electrical circuits, especially in computers: a logic circuit is constructed from AND, OR and NOT gates. Inputs generally designated as A and B, with C, D, E... if required. Voltages are taken as either zero for a logical binary 0 (off) and 3-5 volts for a logical binary 1 (on). The amount of voltage required for a positive value depends on the technology, for example, whether CMOS or TTL.
The link between Boolean algebra and digital computers was not seen until Claude Shannon recognised and developed it in a paper of 1937, showing that Boolean algebra and binary arithmetic could be used to simplify the arrangement of electromechanical relays in telephone routing switches. This was an important step because it meant that circuits could be simplified by applying the rules of Boolean algebra and a connection was made between the On and Off states of electromechanical relays and the 1s and 0s of binary numbers. At this time electrical circuits were large and cumbersome, being made from electromechanical relays and vacuum tubes: any simplification and reduction in size of circuits was beneficial and the link with binary introduced the idea that electronic computers could also use binary. Shannon showed that electrical switches could implement Boolean logic, though it was still some time before this was applied to digital computers, these being still analogue and using denary numbers.
Logic gates are electronic circuits that perform the Boolean functions. Each Boolean operation has a corresponding symbol. Most gates have two inputs and one output, apart from NOT, which has a single input and output. Gates are used in combination to implement extended and complex circuits, usually after simplification through truth tables or Boolean algebra.
Design a circuit that implements the cat choosing formula, either as switches or gates.
Film: Boolean Algebra Part 1
There are a number of laws for Boolean algebra: see here and here. The first shows that in Boolean algebra OR is equivalent to addition and AND is equivalent to multiplication; hence the symbol for OR is '+' while that for AND is '.'. OR is also equivalent to parallel circuits while AND is equivalent to switches in series. It then moves on to the Boolean identities:
Try these with A=0 and A=1:
A + 0 = A
A + 1 = 1
A + A = A
A + 'A = 1
0.A = 0
1.A = A
A.A = A
A.'A = 0
''A=A (double NOT A)
Commutative property: A+B = B+A; AB=BA
Associative property: A+(B+C) = (A+B)+C; A(BC) = (AB)C
Distributive property: A(B+C) = AB + AC; factorize: AB + AC = A(B+C); (A+B).(A+C) = A+(BC)
Useful rules for simplifiaction:
Films: Boolean Algebra Part 2 Boolean Algebra Part 2
Try analysing:
All men are mortal; Socrates is a man; therefore Socrates is mortal.
1: P x M = P (all persons are mortal - Persons and Mortal = Persons)
2: S x P = S (Socrates is a person - Socrates AND Person = Socrates)
3: S x (P x M) = S (substituting P x M for P)
4: (S x P) x M = S (associative law)
5: S x M = S (S x P = S by 2, above)
The last step shows that Socrates AND Mortal produces Socrates; AND is equivalent to intersection so this is the intersection of Socrates and Mortal (try a Venn diagram).
Imagine you are buying a cat and your requirement is: male, neutered, white or tabby, or female, neutered, any colour but white or any black cat, regardless of other qualities. Write out the Boolean expression for this using the first letter of each word. Then take any given cat e.g. male, neutered, ginger. Replace each letter with a 1 for true and a 0 for false. The expression can now be simplified using the rules for OR, AND and NOT. Try different forms of cat.
Make up some similar Boolean expression for buying clothes and take it to a shop!
Exam example: simplify A AND (NOT A OR B); simplify algebraically and confirm with a truth table.
Reverse this: simplify A OR (NOT A AND B): simplify algebraically and confirm with a truth table.
If the output of a gate is inverted then its function will be that of its opposite inverted.
e.g. the output of an OR gate (A + B) is {0 1 1 1}; inverted this is '(A + B) = {1 0 0 0}. '(A + B) is the NOR function.
This is equivalent to ((NOT A) AND (NOT B)): A.B has output {0 0 0 1}; if the inputs are inverted the output is {1 0 0 0}, the same as '(A+B).
Thus the output of an OR gate inverted - '(A + B) - is its opposite inverted ((NOT A) . (NOT B))
Show with truth tables.
e.g. the output of an AND gate (A.B) is {0 0 0 1}; inverted this is '(A.B) {1 1 1 0}. '(A.B) is the NAND function.
This is equivalent to ((NOT A) + (NOT B)): A+B has output {0 1 1 1}; if the inputs are inverted the output will be {1 1 1 0}, the same as '(A.B).
Thus the output of an AND gate inverted - '(A.B) - is its opposite inverted ((NOT A) + (NOT B))
Show with truth tables.
By Boolean Algebra:
'(A + B) becomes ((NOT A) AND (NOT B)) - the NOT is broken and settles on each operand and the operator switches from AND to OR. This is easier to see when the NOT operator is shown with a bar across an expression.
'(A.B) becomes ((NOT A) OR (NOT (B)) - he NOT is broken and settles on each operand and the operator switches from OR to AND.
These laws allow Boolean expressions to be converted to forms that require only (NOT and OR) or (NOT and AND): these are simplified to NOR and NAND.
See here.
Films: De Morgan's Theorem, Boolean Analysis 1, Boolean Analysis 2, Boolean Analysis 3 (sample circuits)
You should be able to identify equivalences:
e.g. '(AB) is equivalent to 'A+'B; in this case the three gates of 'A+'B can be reduced to one NAND gate: '(AB)
e.g. '(A+B) is equivalent to 'A.'B; in this case the three gates of 'A.'B can be reduced to one NOR gate: '(A+B)
e.g. '(ABC) is equivalent to 'A+'B+'C; in this case the four gates of 'A+'B+'C can be reduced to one NAND gate: '(ABC)
e.g. '(A+B+C) is equivalent to 'A'B'C; in this case the four gates of 'A'B'C can be reduced to one NOR gate: '(A+B+C)
Make up some expressions that include inverted expressions and pass them to other members of the class to simplify.
The output of XOR is {0, 1, 1, 0}. We are now in a position to see this as: A'B + 'AB: see the circuit here (bottom of page).
Go to this web site: logic.ly Go to the Try Online version. Enter circuits that you have encountered in your learning so far e.g. A+B(C+D) (from an AQA paper).
A + B . 0 + A . 1
A + 'A + B
'(A + B) + A + B
'A . 'B + A
' A + A . 1 + B . 0
{
A copy of this can be found here.
The aim of this software is to familiarise you with the notation of formal logic. Work through the situations and enter the propositional logic in the edit box to provide safe solutions to each problem.
A half adder performs addition of two bits without carry input. This is fine if you only want to do 0+0, 0+1 or 1+0 but no use if you want to go beyond 1 bit of output. A full adder takes account of carry input from a lower order bit or the carry flag. To add two bytes in an 8 bit processor you would have to add the lower order bytes followed by the higher order bytes; if the highest bit in the lower order bytes generates a carry then this would have to be taken into account when adding the higher order bytes. The last carry will be stored in the carry flag so that it can be taken into account in subsequent operations.
The half adder uses a XOR gate for the output bit because the output is 1 only for 0+1 and 1+0; for 1+1 the output is 0 carry 1. It uses an AND gate for the carry as only A=1 and B=1 will generate carry=1.
Adders are central to the design of CPUs and microprocessors.
An XOR gate can be implemented using 4 NAND gates or 5 NOR gates. Link. Trace the 4 combinations of 0 and 1 to demonstrate that the arrangement works.
}