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
1 answer

Show that $A\subseteq B$ if and only if for any set $C$, one has $(A\cup C)\subseteq (B\cup C)$

Show that $A\subseteq B$ if and only if for any set $C$, one has $(A\cup C)\subseteq (B\cup C)$ $\exists x\in A\cup C \land \exists x\in B\cup C$ $(\exists x\in A\lor \exists x\in C) \land (\exists x\in B\lor \exists x\in C)$ $(\exists x\in A\land…
Danxe
  • 1,695
0
votes
1 answer

tautologies and truth values

I have no idea how to start. really appreciate some help here. Let P and Q be propositions. A statement S (involving P , Q ) is called a tautology iff for any truth-values of P and Q , the statement S is true. Show that the following statements are…
0
votes
1 answer

How Do You Show That There Exist Infinitely Many Organic Tautologies?

This question takes inspiration from this question. A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula itself are not tautologies. For example, C C p q C C q…
0
votes
1 answer

Disjunction Elimination Proof

P∨(Q∨R) ⊢ Q∨(P∨R) Proof: 1.) P∨(Q∨R) Assumption 2.) P Assumption 3.) P∨R 2.) Disjunction Introduction 4.) Q∨(P∨R) 3.) Disjunction Introduction 5.) Q∨R Assumption 6.) Q Assumption 7.) Q∨(P∨R) 6.) Disjunction Introduction 8.)…
Nate
  • 323
0
votes
1 answer

Epress $\exists! x P(x)$using universal quantifications, existential quantifications and logical operators

Epress the quantification $\exists! x P(x)$, using universal quantifications, existential quantifications and logical operators. Does anyone have an idea?
0
votes
2 answers

Prove propositional logic by resolution.

Prove $$[(p→q) \wedge (qr→s)]\to [pr→s],$$ which is the same as $$[(\lnot p\lor q) \wedge (\lnot (qr) \lor s)]\to [\lnot (pr) \lor s]$$ I believe it can just be done with algebra rules, but I got stuck at the end. And this is not a programming…
PTN
  • 205
0
votes
1 answer

Admissible rule in classic logic

The classical propositional logic admits the concept of admissible rule, and would like some examples of propositional calculus with the 'admissible rule', on wikipedia I don't quite understand...
Jianluca
  • 379
0
votes
1 answer

How do I notate a proposition with multiple conditions?

Lets's say I have the predicates: F(x) means x is even G(x) means x is a prime number and we take the universe of discourse to be the set of natural numbers N = {1,2,3,...} How do I notate a proposition such as: "Every number that is a prime number…
x3nr0s
  • 145
0
votes
3 answers

Propositional logic problem: Sales, expenses and happiness of the boss

Either sales will go up and the boss will be happy, or expenses will go up and the boss won’t be happy. Therefore, sales and expenses will not both go up. I know the solution is that the conclusion is wrong, but I don't see why. I would say…
0
votes
0 answers

Expansion Of A algebric term

While doing a coding for software I fell upon in the need to expand the following expression $(A \land B) \land (C \land (D \lor (E \land f)) \land (g \lor h \lor i))$ I tried it and result I got is following $$((A \land B \land C \land D )\lor( A…
0
votes
2 answers

simplification of a propositional statement

Write the formula which is equivalent to the formula $$\neg (p\leftrightarrow(q\to(r \lor p)))$$ and contains the connectives AND ( $\land$ ) and NEGATION ( $\neg$ ) only.
-1
votes
1 answer

Propositional Calculus - Validity

I have the following question: I have drawn a truth table below: From the table I believe that the answer is not C. However I am not sure whether the premise is incorrectly defined as the premise and conclusion are entirely unrelated, or whether…
-1
votes
1 answer

Is my interpretation of these propositional formulas correct?

We define two propositions P and Q as follows. P: Victoria studies hard for the final exam. Q: Victoria desperately wants to ace the final exam. (a) Translate each of the following statements into a propositional formula that uses P and Q. No…
-1
votes
1 answer

Solving box proofs problem

I'm trying to solve this box-proof puzzle but I don't understand how to complete it as I need to somehow assume $A0$ or $\neg\neg B2$. I've used a truth-table solver to confirm that this is a tautology so it must be solvable using box…
Ozzy
  • 385
-1
votes
1 answer

Why is $\neg(P\land Q)$ equivalent to $\neg P\lor\neg Q$?

Why is $\neg(P\land Q)$ equivalent to $\neg P\lor\neg Q$, and how do we prove it? Thanks!
abla
  • 7