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?”
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 ~
Symbol in Electronics
What does it do
Inverts what is ever inputted into it.
Truth Table
A | Not A |
---|---|
0 | = 1 |
1 | = 0 |
Symbol in logic
^ or AND or ,
Symbol in Electronics
What it does
Takes >1 inputs and if both inputs are true, outputs true.
Truth table
A | B | A and B |
---|---|---|
1 | 1 | = 1 |
1 | 0 | = 0 |
0 | 1 | = 0 |
0 | 0 | = 0 |
Symbol in Logic
V, or, “OR”
Symbol in Electronics
What it does
Takes > 1 inputs, if any of the inputs are true than the output is true.
Truth Table
A | B | A or B |
---|---|---|
1 | 1 | = 1 |
0 | 1 | = 1 |
1 | 0 | = 1 |
0 | 0 | = 0 |
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
Truth Table
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
Truth Table
A | B | A => B |
---|---|---|
1 | 1 | = 0 |
1 | 0 | = 0 |
0 | 0 | = 1 |
1 | 0 | = 1 |
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.
TK to finish TODO: finish
TODO: finish this TK
Modern computers use logic gates to operate. You should have an understanding of logic gates from the above.
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.
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.
The symbol “≡” is used to show an equivalence relation.
Facts
≡ is reflexive ≡ is transitive ≡ is symmetric
There are some rules we can use to simplfy propositional formulae.
Communicative Law
AB = BA, A + B = B + A
Examples: 6 * 2 = 12 and 2 * 6 = 12 3 + 4 = 7 and 4 + 3 = 7
Assiocative Law
a(bc) = ab(c) = abc
Examples: (2 + 4) + 5 = 6 + 5 = 11 2 + (4 + 5) = 2 + 9 = 11
Distributive Law
a(b+c) = ab + ac
Example: 3 × (2 + 4) = 3 * 6 = 18 3 × 2 + 3 × 4 = 6 + 12 = 18
Demorgans’ Laws
(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/]
Miscelanous rules
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
TK put questions from tutorial here
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 ¬.
In this section we will explore logic gates some more, by looking at the family of not / exclusive gates.
Symbol in Logic
None
Symbol in Electronics
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.
Truth Table
A | B | A xor B |
---|---|---|
1 | 1 | = 0 |
0 | 1 | = 1 |
1 | 0 | = 1 |
0 | 0 | = 0 |
Symbol in Logic
None
Symbol in Electronics
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.
Truth Table
A | B | A xor B |
---|---|---|
1 | 1 | = 0 |
0 | 1 | = 1 |
1 | 0 | = 1 |
0 | 0 | = 1 |
All boolean functions can be created using either XOR or NAND gates.
Binary is a numbering system that consists of 0 and 1s.
Converting decimal to binary
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
Let’s look at why this worked: System | 1 | 2 | 4 | 8 | 16 —|—|—|—|—|— Binary | 0 | 1 | 1 | N/A | N/A
This is because 6 can be broken into 2 and 4, which is why it’s represented in binary as that.
Binary Addition
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
011
half-adder
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.
Truth Table
P | Q | Carry | Sum |
---|---|---|---|
1 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 |
0 | 0 | 0 | 0 |
Full-adder
The full adder allows you to carry-in as well as carry-out.
Watch this video for a better understanding
https://www.youtube.com/watch?v=VPw9vPN-3ac
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
http://www.electronics-tutorials.ws/combination/comb_7.html
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.
Twos complement
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:
So, invert all digits and add 1. Simple.
If you want to know why this works, click here
Addition in Binary, revisited
A carry that goes off the end can often be ignored, for example:
-1 + -3 1111
Subtraction in binary
Treat this as addition but negate the second operand. So 4 - 3 is just 4 + (-3)
Which is just
0100
Overflow
An example of this is 4 + 7
0100
The correct result, 9, is too big to fit into 4 bit representation.
If both inputs to an addition have the same sign, and the output sign is different, overflow has occured.
Overflow cannot occur if the signs differ.