EA2

claude

Proposition vs. predicate

A proposition has no variables and is true or false. A predicate contains variables and becomes a proposition once the variables are given values or quantified.

Predicate

A statement with variables, like P(x): "User x has administrator privileges." It has no truth value until x is specified.

Universal quantifier (∀)

"For all / every." ∀x P(x) means P holds for every x in the domain.

Existential quantifier (∃)

"There exists / at least one / some." ∃x P(x) means P holds for at least one x.

Negation of ∀x P(x)

∃x ¬P(x)

Negation of ∃x P(x)

∀x ¬P(x)

Negation of "All users have passwords"

∃x(User(x) ∧ ¬HasPassword(x)), meaning there is a user without a password.

Negation of "There exists a bug in the system"

∀x ¬Bug(x), meaning no x is a bug.

Negation of ∀x(P(x) → Q(x))

∃x(P(x) ∧ ¬Q(x))

Negation of a conditional P → Q

P ∧ ¬Q

Translating "All/Every A is B"

∀x(A(x) → B(x)). Use → with ∀, never ∧.

Translating "Some A is B"

∃x(A(x) ∧ B(x)). Use ∧ with ∃, never →.

Symbolize: "There exists a server that is always online"

∃x(Server(x) ∧ AlwaysOnline(x))

Symbolize: "Every algorithm terminates"

∀x(Algorithm(x) → Terminates(x))

Symbolize: "Every database table has a primary key"

∀x(Table(x) → HasPrimaryKey(x)). Choices with ∃, a reversed arrow, or ∀ with ∧ are wrong, so the answer was E (none of the above).

Let P(x): "User x has admin privileges." "All users have admin privileges" is

∀x P(x)

Let T(x): "Packet x is dropped." "At least one packet is dropped" is

∃x T(x)

Let R(x,y): "Process x communicates with server y." "Every process communicates with some server" is

∀x∃y R(x,y)

∀x∃y R(x,y) vs ∃y∀x R(x,y)

∀x∃y: each x has its own y (possibly different). ∃y∀x: one single y works for every x. Quantifier order matters.

Predicate logic is useful in IT for

Database queries (also specifications, verification, and AI rules). Not graphics rendering, arithmetic only, or file compression.

Categorical syllogism

Reasoning with "All/Some/No" statements. Example: All programmers use an IDE; Alice is a programmer; so Alice uses an IDE.

Hypothetical syllogism (HS)

P → Q, Q → R, therefore P → R. It chains conditionals.

Example of HS

If user logs in, session starts. If session starts, resources are accessible. Therefore, if user logs in, resources are accessible.

Disjunctive syllogism (DS)

P ∨ Q, ¬P, therefore Q.

Example of DS

Either the server is online or the backup runs. The server is not online. Therefore the backup runs.

Modus ponens (MP)

P → Q, P, therefore Q. It affirms the antecedent.

Example of MP

If code is correct, program runs. Code is correct. Therefore program runs.

Modus tollens (MT)

P → Q, ¬Q, therefore ¬P. It denies the consequent.

Example of MT

If network is stable, connection holds. Connection fails. Therefore network is not stable.

Simplification

P ∧ Q, therefore P. Example: System is secure AND reliable, so the system is secure.

Conjunction

P, Q, therefore P ∧ Q. Example: System is secure; system is reliable; so secure AND reliable.

Addition

P, therefore P ∨ Q. Example: System is secure, therefore secure OR vulnerable.

Resolution

P ∨ Q, ¬P ∨ R, therefore Q ∨ R.

Fallacy: denying the antecedent

P → Q, ¬P, therefore ¬Q. INVALID.

Fallacy: affirming the consequent

P → Q, Q, therefore P. INVALID.

Why is "If correct password then access granted; user did not enter correct password; therefore access denied" invalid?

It denies the antecedent (¬P, therefore ¬Q). Access could be granted another way.

Why is "All programs terminate; Program X crashed; therefore X terminated successfully" invalid?

The conclusion contradicts the second premise and does not follow from the argument form. Answer: Invalid.

Valid: "All secure websites use HTTPS; portal.dlsud.edu.ph is a secure website; therefore it uses HTTPS"

Valid. It is a universal instantiation plus modus ponens.

Universal Instantiation (UI)

∀x P(x), therefore P(c) for any specific element c. Example: All applications require memory; Photoshop is an application; so Photoshop requires memory.

Universal Generalization (UG)

P(c) for an arbitrary c, therefore ∀x P(x). Example: For an arbitrary server, if it is a server it has an IP address; so all servers have an IP address.

Existential Instantiation (EI)

∃x P(x), therefore P(c) for some new, unnamed element c. Example: Some website is vulnerable; so example.com is vulnerable.

Existential Generalization (EG)

P(c) for a specific c, therefore ∃x P(x). Example: Database Oracle is scalable; so there exists a database that is scalable.

UI vs EI

UI picks ANY element from a ∀ statement. EI picks a SPECIFIC but unknown element from a ∃ statement.

UG vs EG

UG goes from an arbitrary element to ∀. EG goes from a specific element to ∃.

Rules for: All students in IT101 can access the lab; Katrina is in IT101; so Katrina can access the lab

Universal Instantiation + Modus Ponens

Rules for: All operating systems manage processes; Linux is an OS; so Linux manages processes

Universal Instantiation (then modus ponens)

Quick ID: "P ∧ Q so P" vs "P, Q so P ∧ Q" vs "P so P ∨ Q"

Simplification vs. Conjunction vs. Addition

Quick ID: "P → Q, ¬Q so ¬P" vs "P → Q, P so Q"

Modus Tollens vs. Modus Ponens

Quick ID: "P ∨ Q, ¬P so Q" vs "P → Q, Q → R so P → R"

Disjunctive Syllogism vs. Hypothetical Syllogism