|
¬, ∃x,∀y (Highest, do first)
|
|
⋀
|
|
⋁
|
|
→ (Lowest, do last)
|
|
Negation
|
|
¬¬A
|
|
Some Conversions
|
|
𝐴 →𝐵≡¬𝐴∨𝐵
|
|
¬(𝐴 →𝐵)≡𝐴∧¬𝐵
|
|
𝐴 →𝐵≡𝐴∧¬𝐵→False
|
|
∧ and ∨ are associative
|
|
(𝐴 ∧𝐵)∧𝐶 ≡𝐴∧(𝐵∧𝐶)
|
|
(𝐴 ∨𝐵)∨𝐶 ≡𝐴∨(𝐵∨𝐶)
|
|
∧ and ∨ are commutativity
|
|
𝐴∧𝐵≡𝐵∧𝐴
|
|
𝐴∨𝐵≡𝐵∨𝐴
|
|
∧ and ∨ are Distributivity
|
|
𝐴∧(𝐵∨𝐶)≡(𝐴∧𝐵)∨(𝐴∧𝐶)
|
|
𝐴∨(𝐵∧𝐶)≡(𝐴∨𝐵)∧(𝐴∨𝐶)
|
|
Conjunction (Conj)
|
𝐴, 𝐵 / 𝐴∧𝐵
|
|
|
Simplification (Simp)
|
𝐴∧𝐵 / 𝐴 and
|
𝐴∧𝐵 / 𝐵
|
|
Addition (Add)
|
𝐴 / 𝐴∨𝐵 and
|
𝐵 / 𝐴∨𝐵
|
|
Disjunctive Syllogism (DS)
|
𝐴 ∨ 𝐵, ¬𝐴 / 𝐵
|
𝐴 ∨ 𝐵, ¬𝐴 / 𝐵
|
|
Modus Ponens (MP)
|
𝐴, 𝐴 →𝐵 / 𝐵
|
|
|
Conditional Proof (CP)
|
From𝐴, derive 𝐵/𝐴 →𝐵
|
|
|
Double Negation (DN)
|
¬¬𝐴 / 𝐴
|
𝐴 /¬¬𝐴
|
|
Contradiction (Contr)
|
𝐴, ¬𝐴 / False
|
|
|
Indirect Proof (IP)
|
From¬𝐴, derive False / 𝐴
|
|
|
Array Data Structure
|
A linear data structure defined as a collection of elements with the same or different data types.
|
|
They exist in both single and multiple dimensions
|
|
|
Terms to understand the concept of Array.
|
o Element − Each item stored in an array is called an element.
|
|
o Index − Each location of an element in an array has a numerical index.
|
|
Array Update Operation
|
|
1. Start
|
|
2. Set LA[K-1] = ITEM
|
|
3. Stop
|
|
Common Features of Linked List
|
||
|
➢Node: Each element in a LL is represented by a node, contains two components:
|
➢Data: The actual data or value associated with the element.
|
➢Next Pointer: A reference or pointer or address to the next node in the LL.
|
|
➢Head: The first node in a LL is called the “head.” It serves as the starting point.
|
||
|
➢Tail: The last node in a linked list is called the “tail.”
|
||
|
➢Data structures can be added to or removed from the LL during execution.
|
||
|
➢Unlike an array, LL is a dynamically allocated DS that can grow and shrink.
|
||
|
➢No elements need to be shifted after insertion and deletion.
|
||
|
➢Various DSs can be implemented using an LL, such as stack, queue, graphs, hash, etc.
|
||
|
➢Linked list contains 0 or more nodes. Last node points to null(address 0)
|
||
|
Linked List: Searching a Node
|
|
LIST-Searching (L,k)
|
|
1. Curr = L.head
|
|
2. While Curr != NULL and Curr.key != k
|
|
3. Curr = Curr.next
|
|
4. return Curr
|
|
Disjunction
|
|
A ⋁ True ≣ True
|
|
A ⋁ False ≣ A
|
|
A ⋁ A ≣ A
|
|
A ⋁ ¬A ≣ True
|
|
Absorption Laws
|
|
𝐴∧(𝐴∨𝐵) ≡ 𝐴
|
|
𝐴∨(𝐴∧𝐵) ≡ 𝐴
|
|
𝐴∧(¬𝐴∨𝐵) ≡ 𝐴∧𝐵
|
|
𝐴∨(¬𝐴∧𝐵)≡𝐴∨𝐵
|
|
AA (Assignment axiom)
|
{𝑄(𝑥/𝑡)} 𝑥 ≔ 𝑡 {𝑄}
|
|
|
Consequence rules (A & B)
|
𝑃 →𝑅 and {𝑅} 𝑆 {𝑄} / {𝑃} 𝑆 {𝑄}
|
{𝑃} 𝑆 {𝑇} and 𝑇 →𝑄 / {𝑃} 𝑆 {𝑄}
|
|
Modus Tollens (MT)
|
𝐴 →𝐵, ¬𝐵 / ¬𝐴
|
|
Hypothetical Syllogism (HS)
|
𝐴 → 𝐵, 𝐵 → 𝐶 / 𝐴 → 𝐶
|
|
Proof by Cases (Cases)
|
𝐴∨𝐵, 𝐴→𝐶, 𝐵→𝐶 / 𝐶
|
|
Constructive Dilemma (CD)
|
𝐴 ∨ 𝐵, 𝐴 → 𝐶, 𝐵 → D / 𝐶 ∨D
|
|
Destructive Dilemma (DD)
|
𝐴 →𝐵, 𝐶 →𝐷, ¬𝐵∨¬D / ¬𝐴∨¬𝐶
|
|
Operations in Arrays
|
|
o Traverse − print all the array elements one by one.
|
|
o Insertion − Adds an element at the given index.
|
|
o Deletion − Deletes an element at the given index.
|
|
o Search − Searches an element using the index or value.
|
|
o Update − Updates an element at the given index.
|
|
o Display − Displays the contents of the array.
|
|
Array Search Operation
|
|
1. Start
|
|
2. Set J = 0
|
|
3. Repeat steps 4 and 5 while J < N
|
|
4. IF LA[J] == ITEM THEN GOTO STEP 6
|
|
5. Set J = J +1
|
|
6. PRINT J, ITEM
|
|
7. Stop
|
|
Linked List: Operations
|
|
➢Accessing Elements/Traversing: Accessing a specific element in a linked list takes O(n) time since nodes are stored in non-contiguous locations, so random access is not possible.
|
|
➢Searching: Searching a node in an LL takes O(n) time, as the whole list needs to be traversed in the worst case.
|
|
➢Insertion: If we are at the position where we insert the element, insertion takes O (1) time.
|
|
➢Deletion a/Destroy the list: Deletion takes O(1) time if we know the element’s position to be deleted.
|
|
Conjunction
|
|
A ⋀ True ≣ A
|
|
A ⋀ False ≣ False
|
|
A ⋀ A ≣ A
|
|
A ⋀ ¬A ≣ False
|
|
Absorption Laws
|
|
𝐴∧(𝐴∨𝐵) ≡ 𝐴
|
|
𝐴∨(𝐴∧𝐵) ≡ 𝐴
|
|
𝐴∧(¬𝐴∨𝐵) ≡ 𝐴∧𝐵
|
|
𝐴∨(¬𝐴∧𝐵)≡𝐴∨𝐵
|
|
AA (Assignment axiom)
|
{𝑄(𝑥/𝑡)} 𝑥 ≔ 𝑡 {𝑄}
|
|
|
Consequence rules (A & B)
|
𝑃 →𝑅 and {𝑅} 𝑆 {𝑄} / {𝑃} 𝑆 {𝑄}
|
{𝑃} 𝑆 {𝑇} and 𝑇 →𝑄 / {𝑃} 𝑆 {𝑄}
|
|
Composition rule
|
{𝑃} 𝑆1 {𝑄} and {𝑄} 𝑆2 {𝑅} / {𝑃} 𝑆1;𝑆2 {𝑅}
|
|
|
If-then Rule
|
{𝑃 ∧𝐶} 𝑆 {𝑄} and 𝑃 ∧¬𝐶 → 𝑄
|
{𝑃} if 𝐶 then 𝑆 {𝑄}
|
|
If-then-else rule
|
{𝑃 ∧𝐶} 𝑆1 {𝑄} and {𝑃 ∧¬𝐶} 𝑆2 {𝑄} / {𝑃} if 𝐶 then 𝑆1 else 𝑆2 {𝑄}
|
|
|
While rule
|
{𝑃 ∧𝐶} 𝑆 {𝑃} / {𝑃} while 𝐶 do 𝑆 {𝑃 ∧¬𝐶}
|
|
|
Array Deletion Operation
|
|
1. Start
|
|
2. Set J = K-1
|
|
3. Repeat steps 4 and 5 while J < N
|
|
4. Set LA[J] = LA[J + 1]
|
|
5. Set J = J+1
|
|
6. Set N = N-1
|
|
7. Stop
|
|
Array Insertion Operation
|
|
1. Start
|
|
2. Create an Array of a desired datatype and size.
|
|
3.Initialize a variable 'i' as 0.
|
|
4. Enter the element at the i-th index of the array.
|
|
5. Increment i by 1
|
|
6. Repeat Steps 4 & 5 until the end of the array.
|
|
7. Stop
|
|
Implication
|
|
A → True ≣ True
|
|
A → False ≣ ¬A
|
|
True → A ≣ A
|
|
False → A ≣ True
|
|
A → A ≣ True
|
|
De Morgan's Laws
|
|
¬(𝐴∧𝐵) ≡ ¬𝐴∨¬𝐵
|
|
¬(𝐴∨𝐵) ≡ ¬𝐴∧¬𝐵
|
|
"An equivalence to be careful with"
|
|
∃𝑥(𝑝(𝑥) → 𝑞(𝑥)) ≡ ∀𝑥𝑝(𝑥) → ∃𝑥𝑞(𝑥)
|
|
Negations of quantifiers
|
|
¬(∀𝑥𝑊) ≡ ∃𝑥¬W
|
|
¬(∃𝑥𝑊) ≡ ∀𝑥¬W
|
|
Formalize English sentences and entire arguments into FOPC
|
|
∀𝑥 quantifies a conditional
|
|
∃𝑥 quantifies a conjunction
|
|
∀𝑥 with conditional for “all,” “every,” and “only.”
|
|
∃𝑥 with conjunction for “some,” “there is,” and “not all.”
|
|
∀𝑥 with conditional or ¬∃𝑥 with conjunction for “no A is B.”
|
|
∃𝑥 with conjunction or ¬∀𝑥 with conditional for “not all A’s are B.”
|
|
UI
|
Universal instantiation requires that 𝑡 is free to replace 𝑥 in 𝑊(𝑥):
|
∀𝑥𝑊(𝑥) / 𝑊(𝑡)
|
There are two special cases for UI:
|
∀𝑥𝑊(𝑥) / 𝑊(𝑥)
|
∀𝑥𝑊(𝑥) / 𝑊(𝑐)
|
|
EI
|
Existential generalization requires that 𝑡 is free to replace 𝑥 in 𝑊(𝑥)
|
𝑊(𝑡) / ∃𝑥𝑊(𝑥)
|
|||
|
EG
|
Existential generalization requires that 𝑡 is free to replace 𝑥 in 𝑊(𝑥):
|
𝑊(𝑡) / ∃𝑥𝑊(𝑥)
|
There are two special cases for EG:
|
𝑊(𝑥) / ∃𝑥𝑊(𝑥)
|
𝑊(𝑐) / ∃𝑥𝑊(𝑥)
|
|
UG
|
Universal Generalization
|
∃𝑥𝑊(𝑥) / 𝑊(𝑐)
|
|||
|
Array Traversal Operation
|
|
1. Start
|
|
2. Initialize an Array, LA. // 1. Initialize an array called LA
|
|
3. Initialize, i = 0. // 2. Set i - 0
|
|
4. Print the LA[i] and increment i. // 3. Repeat Steps 4-5 while i < N
|
|
5. Repeat Step 4 until the end of the array. // 4. Print LA[i]
|
|
6. End // 5. Increment the value of i by one. (Set i = i + 1)
|
|
➢An abstract data type (ADT) in data structure is a data type defined with the help of some attributes and some functions
|
|||
|
➢An abstract data type in the data structure can be
|
➢A list data structure
|
➢A stack data structure
|
➢A queue data structure
|
|
➢Linked List: A LL is a linear data structure constructed like a chain of nodes where
|
➢Each node contains a data field
|
➢A reference(link/address/array-Indices) to the next node in the list.
|
|
|
➢Unlike Arrays, Linked List elements are not stored at a contiguous location.
|
|||
No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.
