CSIT111: Pre-Finals

LOGIC

the study of correct reasoning

LOGIC

analyzes propositions, which are declarative

sentences that are either true or false, but not

both at the same time

PROPOSITIONS

The following are examples of what:

● Canberra is the capital of Australia (True)

● Casablanca is found in Spain (False, it is in Morocco)

● Today is Wednesday (This can be true or false but not at the same time. I may be saying or typing this on a Wednesday, but you may be hearing or reading this on, say, a Monday)

Simple Propositions

Compound Propositions

TYPES OF PROPOSITIONS

Paradox

it is true and false at the same time. It is false if taken at face value, which makes the statement true, making it false again, then true again, and it goes on and on

Simple Propositions

These propositions have only one idea and no logical connectives or operators to connect other ideas.

Simple Propositions

Examples of these propositions:

> 1 + 1 = 2

> The quick brown fox jumps over the lazy dog.

> The five boxing wizards jump quickly.

Compound Propositions

These propositions have at least two simple propositions connected using logical connectives or operators)

Compound Propositions

Examples of these propositions:

> Amir is from India, but he lives in Singapore.

> Belle is Filipina and Clarice is French.

> If David is American, then he has read the New York Times.

Logical Operators

denote certain relationships between simple propositions

Truth values

determine whether something is true or false

True/T and False or 1 (T) and 0 (F)

Truth values have two common representations which are

Truth tables

list all possible combinations of truth values of the simple propositions in a compound proposition.

Tautology

Contradiction

Contingency

TYPES OF COMPOUND PROPOSITIONS

Tautology

always true no matter the truth value of the individual simple propositions

Contradiction

always false no matter the truth value of the individual simple propositions

Contingency

neither tautology nor contradiction

Negation (NOT)

states the opposite truth value of a statement.

Negation (NOT)

It is the only unary operator as it takes only one statement.

Negation (NOT)

can be denoted by -p, ~p, p', p̄

In C programming, it is represented by an !

CONJUNCTION (AND)

a proposition where all the simple statements connected must be true for the entire compound statement to be true.

CONJUNCTION (AND)

This can be denoted by ^

In C programming, it is represented by && (two ampersands)

DISJUNCTION (OR)

a proposition where at least one of the simple statements connected must be true for the entire compound statement to be true.

DISJUNCTION or INCLUSIVE DISJUNCTION (OR)

This is denoted by "v"

In C programming, it is denoted by ||

EXCLUSIVE DISJUNCTION (XOR)

a proposition where exactly one of the two simple statements connected must be true for the entire compound statement to be true.

EXCLUSIVE DISJUNCTION (XOR)

This is denoted by "⊕"

p ⊕ q, is read as p or q but not both

CONDITIONAL/IMPLICATION (IF)

proposition which is false only when its conclusion q is false and its hypothesis p is true

CONDITIONAL/IMPLICATION (IF)

This is denoted by p->q and is read as "if p then q" or "p implies q"

Biconditional (IFF)

a proposition which is true when both propositions are true, or when both are false.

Biconditional (IFF)

This is denoted by "↔"

p ↔ q and is read as "p if and only if q"

Sets

well-defined collections of objects

Elements

These are objects in sets. These are enclosed in curly braces {} and separated by commas

sets, set elements

Uppercase letters denote ___, lowercase letters can denote ___

In Or Out

The Symbol ∈ denotes membership and is read "is an element of", "belongs to" or "is in"

> Similarly, the symbol ∉ is read as "is not an element of", "does not belong to", or "is not in"

List or roster method

description method

set builder or rule method

Ways to describe a set

List or roster method

This method lists every element of the set

Ex: A = {3, 6, 9, 12, 15, ..., 30}

Description method

This method gives an informal verbal description of the set's element

Ex: A is the set of all multiples of 3 from 1 to 30

Set builder or rule method

This method gives a formal verbal description or rule to describe the sets elements

Ex: A = {x|x is a multiple of 3 ^ x <= 30}, read as "Set A is the set of all x such that x is a multiple of 3 and x is less than or equal to 30."

Cardinality

the number of elements in a set.

> For set A, it is denoted be n(A).

Finite sets

These sets have countable numbers of elements

Infinite sets

These sets have an infinite number of elements. > Cardinality is infinite (∞)

Null/Empty set ∅ or {}

These sets have no element (cardinality = 0)

Singleton set

This set has only one element (cardinality = 1)

Equal sets

have the same elements (no matter the repetition or order)

Subset

(A ⊆ B)

A is a ___ of B if all elements in A are in B. Also read as "A is contained by B".

Superset

(B ⊇ A)

B is a ___ of A if it contains all elements of A. Also read as "B contains A".

Proper subset

(A ⊂ B)

A is a ___ of B if A is a subset of B and B has at least one element not in A.

Proper Superset

(B ⊃ A)

B is a _____ of A if it contains all elements of A and one or more elements not in A.

Power Sets

The set of all possible subsets of a set A.

> Cardinality (Size): If a set has n elements, its power set contains 2^n elements.

universal set U

the set containing all elements for a particular discussion

Union

Combines all elements from both Set A and Set B.

> denoted by A U B

Intersection

The set of elements common to both Set A and Set B

> denoted by A ∩ B

Complement

Elements in the Universal Set (U) that are NOT inside Set A

> denoted A' or

Difference

Elements found in Set A but NOT in Set B.

> denoted by A - B

Venn diagrams

These can be used to illustrate the contents of sets and where they belong

Algorithm

a step-by-step way of getting something done, just like computer programs or processes.

Flowchart

a diagram depicting the flow and logic of a process or system such as a computer program or an algorithm

Flowchart

It uses simple shapes and a set of standard symbols to define the type of step and the sequence

Flowchart

helps you outline a computer program or process or algorithm clearly•

Data

information manipulated internally by a computer.

Data Structure

way of organizing data in a computer so it could be used effectively.

Array

holds items of the same type

Element

an item stored in the array.

Index

Location of an element in an array. It is used to identify the element. The index of the first element of an array is typically 0

Linked List / List

a data structure that decides the arrangement of data with a pointer (reference to the memory address of data) to the next element with the option to pointer to the previous one

Stack

follows the Last In, First Out (LIFO) principle. Elements are added and removed from the same end, known as the top

Push

insert an item on top of the stack.

Pop

remove an item from the top of the stack.

Queue

follows the First In, First Out (FIFO) principle. Elements are added at one end called the rear, and removed from the other end called the front

Enqueue

insert an item into the rear of the queue.

Dequeue

remove an item from the front of the queue.

Tree

nonlinear hierarchical data structure consisting of nodes connected by edges.

Node

corresponds to data.

Branch / Edge

connects a node to another.

Root

highest-order node. Has no parent.

Child

node branching off under a node

Parent

original data before it begins to branch

Sibling

has a common parent and is on the same level.

Leaf

lowest-order node. Has no children.

Internal node

a node that is not a leaf.

Subtree

tree of all descendants of a node

Binary Tree

a type of tree which has up to two children.

Terminator, Process, Data or Input/Output, Directional Flow, Decision

Symbols used in Flowcharting

Terminator

> This symbol is represented by an oblong/oval/pill

> marks the start and the ends of the process

Process

> represented by a rectangle

> marks an action or step in the process

Input/Output

> represented by a parallelogram

> marks where a system input or a system output takes place

Directional Flow

> represented by arrows with the arrowhead indicating the direction

> represent the paths a flowchart's user takes between steps

> dotted or dashed arrows can represent alternate paths

Decision

> represented by a diamond

> represent decisions to be made, often based on a true.false or yes/no questions

Sequential Logic

simplest type of logic simply executing instructions one after another/one at a time

Conditional Logic

type of logic deciding the next instructions to follow based on certain conditions

Iterative Logic

Type of logic repeating execution of a set of instructions

Computer programs

collections of text that commands computers to perform algorithms.

Programming languages

allow users to write programs to the computer

Machine language

Assembly language/low-level language

high-level language

Types of Programming Languages

Machine language

consists of only 0s and 1s. Can be understood by hardware but not by humans.

Assembly language/Low-level language

machine-centric language executed quickly. Humans will have some difficulty understanding this sort of language.

> Examples: x86 assembly, x64 assembly.

High-level language

highly-readable languages easily understood by humans. Must be converted to low-level languages by either interpreters or compilers.

> Examples: C, C++, Python, Java, C#, FORTRAN, COBOL

C

a procedural language developed by Dennis Ritchie and is widely used for system development

C++

language with highly similar syntax to C developed by Bjarne Stroustrup. Suitable for system development while also being suitable for object-oriented programming. It is used in systems programming (including embedded systems such as Arduino [9]), and application programming

Java

another object-oriented programming language developed by James Gosling which can run on different hardware as long as a Java Virtual Machine (JVM) is installed

Widely used in Android