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
2 answers

How to determine if the following logical statement is true or false?

$$\exists n\forall m ((n+8) \mid ((m+1)^{n+8} - m -1))$$ Where $n$ and $m$ are natural numbers. How can I determine whether this expression is true or false? What I have done thus far is the following ... I rewrite it as $\exists n\forall m…
0
votes
0 answers

Which phone has rung? Propositional Logic understanding.

A phone rang in a class. Four students each have their own phone. We consider these four statements : $P1$ : $\mathbf James$ : It's not my phone that rang. $P2$ : $\mathbf Marie$ : It's James' phonee that rang Sir. \ $P3$ : $\mathbf Jacob$ : No…
Mario SOUPER
  • 149
  • 1
  • 7
0
votes
0 answers

Propositions problem

Not all three balls are of the same colour. (Colours are black or white.) Among the three balls, there is exactly one white ball, or there is exactly one black ball. I know they are are logically equivalent. However, i don't know how to formulate…
game game
  • 21
  • 2
0
votes
2 answers

Rewrite logical formula to one with only '$\to$' and '$\neg$'?

How can I write: $A \to B ∧ B \to A $ as a statement with only '$\to$' and '$\neg$' ?
Raymond
  • 155
0
votes
2 answers

Simplification of $(p\to r) \,\leftrightarrow\, (q\to r)$

I got $$((p\wedge \neg r)\,\vee\, (\neg q \vee r))~\wedge~ ((q\wedge \neg r) \,\vee\, (\neg p \vee r))$$ but I don't know what to do next. I can't apply any laws here so I am really confused.
Rongday
  • 29
0
votes
1 answer

translation of assertion

I have been thinking about translating an assertions into a suitable formal logical language :" If they have vanilla, then I'll also have that, but otherwise I'll have chocolate." Since I am not sure what "But" really means, I tried two ways to…
0
votes
2 answers

Question from Propositional and First Order Logic.

Let a, b, c, d be propositions. Assume that the equivalences a ↔ (b V ~b) and b ↔ c hold. Then the truth value of the formula (a ∧ b) → ((a ∧ c) ∨ d) is always? I solved using hint - a ↔ (b V ~b) a ↔ 1 And, b ↔ c Given equation, (a ∧ b) → ((a ∧ c) …
Amar
  • 847
0
votes
1 answer

Proving p → q ⊢ (p ∨ r) → (q ∨ r)

Can you prove this conclusion follows from the premiss without the use of any tautology? I've been trying to do it but I haven't succeeded without using the tautology equivalences. p → q ⊢ (p ∨ r) → (q ∨ r)
0
votes
2 answers

Prove a set is not a complete set of connectives

Prove that the set of {not, xor, iff} is not complete. My question is in when defining a predicate how can you do it so that each of the above connectives are satisfied. The only truth assignments i know of is 0, 1 however i don't think it would…
user400098
0
votes
1 answer

How to check for tautologic equivalence using resolution method?

I have following task in my study materials: Have formulas $\varphi = (a \implies b) \iff c, \psi = \lnot a \lor (b \implies c)$. Determine whether the formulas $\varphi$ and $\psi$ are tautologically equivalent using the resolution method. What I…
0
votes
1 answer

Can I discharge this kind of assumption(conditional proof of propositional logic)?

I know the mechanism of discharge of assumption in propositional logic. However, I wonder this kind of assumptions could be discharged: $$\begin{array}{llll} \text{Used premises}&\text{Line}&\text{Proposition}&\text{Used…
Eric
  • 4,517
  • 1
  • 18
  • 36
0
votes
1 answer

Is every formula with a unique minimal model equivalent to a horn clause?

I know that every horn clause has an unique minimal model. But what about the other way around? Is every formula that has a unique minimal model always equivalent to a horn clause?
0
votes
2 answers

Simplify this propositional statement

how can I simplify $(p\to q)\wedge(q\to r)$? I need to find out for which $p, q, r$ this is true, without using truth tables.
0
votes
0 answers

How to read (A or B) equivalent to C.

I'm following a YouTube tutorial on propositional logic, but have noticed the following well formed formula example and I'm struggling to make sense of it: $$ \lnot [(A \lor B) \equiv (E\supset C)] $$ How should this be interpreted. At the moment -…
R4D4
  • 149
0
votes
1 answer

What biconditional has its negation equivalent to this given disjunction?

Working basic logic problems to solidify my grasp on the elementary concepts, I found the following kind of question a bit unclear and I am not sure whether my reasoning is appropriate to solve it. An example of such a question is: For which…
user409521