# Mathematical Logic

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.

# Propositional logic

Propositions can only be true or false.

# Intrepetations

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.

# Propositional symbols

There are about 500,000 ways to represent logic symbols so here are the most common ways

# Not

**Symbol in logic**

¬ or ! or ~

**Symbol in Electronics**

**What does it do**

Inverts what is ever inputted into it.

**Truth Table**

# Conjunction or and

**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**

# Disjunction, “or”

**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**

# Equivilance

**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

# Implication

**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**

# 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.

# Logical Puzzles

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.

# Semantic Conseqeuence

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.

# Circuit equivalence

Two circuits are equivalent if they produce the same output given the same input

# Formula equivalence

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.

**Facts**

≡ is reflexive ≡ is transitive ≡ is symmetric

# Simplfying propositonal formulae

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

# Boolean Functions

**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.

# XOR

**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**

# NAND

**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**

# 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.

**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

**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

**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:

- Find the complement (EG convert all 0’s to 1’s and all 1’s to 0’s)
- Add 1 to the complement

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

- 1101 1100 with a carry of 1 that goes all the way to the left, it can be ignored.

**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.

*Originally published at **brandonskerritt.github.io** on November 25, 2017.*