Logic has been used for thousands of years, from philosophy to mathematics and now to artificial intelligence. Logic is concerned with the truth and falsity of statements. The logic we will be studying will be answering the question: “when does a statement follow from a set of statements?”
Note to the reader
I have previously written about logic here and therefore this article will be relatively short when it comes to explaining everything about logic. If you want to understand logic, please read the article I have written on logic. This is just an expansion on what we have learned.
Propositions can only be true or false.
An intrepretation assigns to a propositional statement a truth value of True or False. True or False can be represented as 0 and 1 respectively.
There are about 500,000 ways to represent logic symbols so here are the most common ways
Symbol in logic
¬ or ! or ~
What does it do
Inverts what is ever inputted into it.
Conjunction or and
Symbol in logic
^ or AND or ,
What it does
Takes >1 inputs and if both inputs are true, outputs true.
Symbol in Logic
V, or, “OR”
What it does
Takes > 1 inputs, if any of the inputs are true than the output is true.
Symbol in Logic <=> or ≡
Symbol in Electronics None, this is a concept not a gate.
What it does A and B must take the same truth value
A B A <=> B 1 1 = 1 0 1 = 0 1 0 = 0 0 0 = 1
Symbol in Logic => or “if a then b”
Symbol in Electronics None
What it does If A is true then so is B
Sorry for the change of pictures. Previously there was an error in this truth table.
Truth under an interpretation
Given an interpretation, I, we can compute the truth value of any formula P under I. That is, given a version of the formula we can computer the truth value.
if I(P) = 1 then we say that P is true under interpretation I. if I(P) = 0 then we say that P is false under interpretation I.
This section may help the reader in understanding logical puzzles.
An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie. You go to the island and meet A and B. A says that “B is a knight” B says that “The two of us are opposite types”
What are A and B?
So we have 2 options, p: “A is a knight”; and q: “B is a knight”
We have 2 options because one of them needs to be a knight. Either both A and B are knaves, which makes B a knight as it told a truth so it lied or A is a knight and is telling the truth that B is a knight.
Options for person A p is true, that is the statement “A is a knight” is true. P => Q p is false, that is the statement “A is a knight” is false. ¬P => ¬Q
Options for person B q is true then q => ¬p q is false then ¬q => ¬p
Now we simply need to construct a truth table for these values
p q ¬p ¬q p => q ¬p => ¬q q => ¬p ¬q => ¬p 0 0 1 1 1 1 1 1 = 1
Then we stop here because we’ve found an interpretation under which they are both knaves which is satisfiable.
Note: The lecture slides for this weren’t helpful and there is no audio for this. Please message me what this is.
Digital Logic Circuits
Modern computers use logic gates to operate. You should have an understanding of logic gates from the above.
General house keeping rules of making circuits
Never combine two input wires
If there are 2 separate inputs, A and B, you cannot combine them into one single wire.
A single input wire can be split partway and used as input for two seperate gates
If you have a single input, A, it can be split into 2 separate wires.
An output wire can be used as input
The output of a wire can be used as an input.
No output of a gate can eventually feed back into that gate
No gates can loop on themselves.
Constructing logic circuits from tables
Given a table, such as the one below, how would we construct a logic circuit for it?
First, work out where it is equal to 1 (true) and then from there formalise it in mathematical logic, from the mathematical logic we can deduce the circuit for it. Sometimes it is easier to guess directly what logic gates are used.
Two circuits are equivalent if they produce the same output given the same input
2 formula are equivalent if they hold the same truth value under every possible interpretation.
On Logical Equivalence
The symbol “≡” is used to show an equivalence relation.
≡ is reflexive ≡ is transitive ≡ is symmetric
Simplfying propositonal formulae
There are some rules we can use to simplfy propositional formulae.
AB = BA, A + B = B + A
Examples: 6 * 2 = 12 and 2 * 6 = 12 3 + 4 = 7 and 4 + 3 = 7
a(bc) = ab(c) = abc
Examples: (2 + 4) + 5 = 6 + 5 = 11 2 + (4 + 5) = 2 + 9 = 11
a(b+c) = ab + ac
Example: 3 × (2 + 4) = 3 * 6 = 18 3 × 2 + 3 × 4 = 6 + 12 = 18
(A ∪ B)’ = (A)’ ∩ (B)’ The first law states that the complement of the union of two sets is the intersection of the complements.
(A ∩ B)’ = (A)’ ∪ (B)’ The second law states that the complement of the intersection of two sets is the union of the complements.
For a good blog post on understanding these laws, click (here)[https://brilliant.org/wiki/de-morgans-laws/]
Not Not A = A A or A and B = A A or not A and B = A and B (A or B) (A or C) = A or B and C
What to do next From this point, turn the circuit into a logical expression and simplfy it using the rules above.
If this is confusing still, maybe this video will help: https://www.youtube.com/watch?v=59BbncMjL8I
Arity The arity of a boolean function is how many arguments the function takes
Boolean function representation
Any boolean can be represented with ^, v, or ¬.
Logic Gates Extended
In this section we will explore logic gates some more, by looking at the family of not / exclusive gates.
Symbol in Logic
What it does
An XOR gate takes >1 inputs and performs exclusive disjunction. The output of an XOR gate is only true if one of its inputs is different to the other input.
Symbol in Logic
What it does
A NAND gate takes >1 inputs and the output is the opposite of an AND gate. The output is true when one or more, but not all, of its inputs are false.
Universality of XOR and NAND
All boolean functions can be created using either XOR or NAND gates.
Binary Numbering System
Binary is a numbering system that consists of 0 and 1s.
Alternatively, you could memorise the powers of 2. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… And then to convert a number into binary, let’s say 6, you build that up from the different powers. So 6 is 011 and then reverse that, 110
Somethings you need to know in binary 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 10
Once you know these basic rules, you can add any numbers together in binary the same way you can add normal numbers. Try this exercise
The half adder is a type of binary adder in electronics that adds together two single binary digits and provides the output plus a carry value.
Note: Boris’ half-adder is overcomplicated, you can achieve the same by replacing 3 of his logic gates with a single XOR gate.
The full adder allows you to carry-in as well as carry-out.
Watch this video for a better understanding
Black Box Notation
We can represent the full adder as a black box, we don’t need to know what happens inside of it, only the inputs and outputs.
4 bit adder
Using blackbox notation, we can create 4-bit adder
Computer Representation of negative integers
A fixed number of bits is used to represent integers: 8, 16, 32 or 64 bits. An unsigned integer can take up all the space available.
You can “sign” a binary number to indicate whether it is negative or not. For example, the number 10 can be represented in 8-bit as 00001010 and -10 can be represented in 8-bit as 10001010
But this sometimes causes a problem, for example, 10000000 represents -0. Whaaatt?? Negative 0? Yes! That’s right, and that’s exactly the problem this causes.
This is where 2’s complement comes into play.
Converting a decimal to twos complement
1) Convert the number to binary, ignoring the sign for now. So 5 is 0101 and -5 is 0101.
2) If the number is a positive number then you are done, no need to go any further. Otherwise…
3) If the number is negative then:
- Find the complement (EG convert all 0’s to 1’s and all 1’s to 0’s)
- Add 1 to the complement
- 1101 1100 with a carry of 1 that goes all the way to the left, it can be ignored.
Originally published at brandonskerritt.github.io on November 25, 2017.