Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
0
votes
0 answers

If $P \iff Q,¬Q$ are proved, what are the inference schemes following from them?

I'm reading Exner's Logic in Elementary Mathematics, there is an exercise in which I should point all the inference schemes, if any in a bunch of statements. There is this one: A point $P$ is called the pole of a line $p$ iff $P$ is not joined to…
Red Banana
  • 23,956
  • 20
  • 91
  • 192
0
votes
0 answers

Rewrite propositions with equivalence.

Rewrite these propositions wih equivalence: $a:(b \, \lor \, c) \Rightarrow (\lnot b \, \lor \, \lnot c)$ $b: (\lnot c \, \lor \, q) \Rightarrow r$ $c: a \Rightarrow (\lnot q \, \land \lnot r)$ I got statements which I have to write in the form…
Muffy
  • 343
0
votes
2 answers

Conditionnal and implication

Ali, Bob, Celia and Danny were making a decision conditional. Bob said that he will attend a given event if Ali does. Celia said that she will go if Bob does. Danny said that he will go if Celia does. Eventually exactly two of them attended the…
user409521
0
votes
1 answer

What do I need to substitute to go from $(P\to Q)\equiv ¬P\vee Q$ to $¬(P\to Q)\equiv ¬(¬P\vee Q)$?

I want to deduce that $$¬(P\to Q)\equiv P\wedge¬Q$$ In the book I'm reading, he suggests to use: $$(P\to Q)\equiv ¬P\vee Q\tag{1}$$ and substitute to get: $$¬(P\to Q)\equiv ¬(¬P\vee Q)\tag{2}$$ I am able to deduce it by negating both sides of…
Red Banana
  • 23,956
  • 20
  • 91
  • 192
0
votes
1 answer

Why commutative law, associative law, distributive law ... are considered to be axioms in propositional logic?

Why commutative law, associative law, distributive law ... are considered to be axioms in propositional logic? Though we can prove them using truth tables.
0
votes
1 answer

Need an explanation for propositional logic.

A Simple SAT Instance: Let $R \supseteq \{p_1, p_2, p_3, p_4, p_5\}$. Let $F = (¬p_1 ∨ p_2) ∧(¬p_2 ∨ p_1) ∧ (¬p_1 ∨ ¬p_2 ∨ ¬p_3) ∧ (p_1 ∨ p_2) ∧ (¬p_4 ∨ p_3) ∧ (¬p_5 ∨ p_3)$. $\left\{p_1, p_2\right\}$ is a model for $F$. Hence, $F$ is…
0
votes
1 answer

Propositional logic: prove equivalence of inconsistent

Given $Γ$ is semantically inconsistent, need to prove: for all propositions $θ$, we have $Γ⊨θ$. "$Γ$ is semantically inconsistent", then there is no truth assignment $A$ such that $A(Γ)=1$. But the definition of entail states: A set of sentences…
yashirq
  • 505
0
votes
1 answer

Propositional logic: is the logic behind my answer correct?

Q: Given the following, can you prove that the unicorn is mythical? How about magical? Horned? "If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal,…
Varoun
  • 1
0
votes
1 answer

What does it mean "p is provable from G"

I´ve just been introduced to this subject, but I am bit confused when it comes to answering some of the question I am given. So, say I have a set of premises G and I am asked to show that a preposition p is provable from G. My question is that if I…
0
votes
1 answer

How to prove tautology from entail?

If $\emptyset$ $\models$ $\phi$, can we say $\phi$ is a tautology because we can entail $\phi$ from nothing?
yashirq
  • 505
0
votes
0 answers

what does it mean by "write an inductive definition for F as a set of pairs"?

Give an inductive definition of the function F , defined by recursion on PROP from the functions H at , H o, H ¬ , as a set F ∗ of pairs Can anyone explain the question and give a hint for answer?
Athena
  • 103
0
votes
1 answer

Uncertainty about the definition of entail

Definition We say that a set of propositions (the "premises") $Γ$ entails a proposition $φ$ (the "conclusion") if for every truth assignment $A$, if $A(φ)$=1 when we have $A(ψ)$=1 for all $\psi$ in $Γ$. Note: if a truth assignment assigns "false"…
yashirq
  • 505
0
votes
1 answer

solution to :If ϕ occurs in a shortest formation sequence of ψ then ϕ is a subformula of ψ

Can anybody help me solve this question? If ϕ occurs in a shortest formation sequence of ψ then ϕ is a subformula of ψ I know that the proof is by induction but I do not specificly know how to solve it.
Athena
  • 103
0
votes
0 answers

Prove (using induction) that no proposition is a proper initial segment of another proposition

I feel very confuse on math logic. For the question above, I don't even know what is the base case. Can anyone give me some hint? This is the definition of proposition: If $P\in Props$, then $P$ is a proposition. And if $\varphi$ and $\psi$ are…
yashirq
  • 505
0
votes
2 answers

is this formula semantically entailed from the empty set of premises?

I did the truth table of the below logic: ((p ∨ q) → r) → ((p → r) ∨ (q → r)) However I didn't quite understand what semantically entailed form the empty set of premises? What that mean exactly? As far as i understand, Whatever P I pick, the…