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

False proof by contradiction?

$P(x)$ is a polynomial, whose degree is either $1$ or $0$ (we do not know exactly which). $Q(x)$ is a polynomial, whose degree is unknown. Assuming that the degree of $P(x)$ is $1$, I prove that Degree of $Q(x) = 1$ $\implies$ Degree of $Q(x) = A >…
-2
votes
1 answer

Is the following a valid argument?

$[ (¬p ∨ s) ∧ (¬ t ∨ ( s ∧ r)) ∧ ( ¬q ∨ r) ∧ ( p ∨ q ∨ t)] \rightarrow ( r ∨ s)$. I have no idea how to go about this proof. I don't see any way to simply to prove that it is correct, truth table is too many rows. What do I do?
-2
votes
2 answers

Use the Fitch System to prove (p ⇒ (q ⇒ r)) ⇒ ((p ⇒ q) ⇒ (p ⇒ r)).

It's really complex and I really need a simple way to do it. I just go blank when I see it. Please help...
-2
votes
2 answers

How can I prove ¬p∨(p∧q) is logically equivalent to p→q?

I've been having difficulty figuring out this problem: ¬p∨(p∧q) = p→q If I use distribution law, I'm stuck with (¬p∨p)∧(¬p∨q) and can't use idempotent law. If I use conditional Law, I get p→(p∧q) and am stuck. Edit: we need to only use the…
-3
votes
2 answers

Can $p$ divide both $a_1 − a_2$ and $a_1 + a_2$?

If $a_1^2 ≡ a_2^2 \pmod p$, then $p$ divides $a_1^2−a_2^2$, so $p$ divides the product $(a_1 − a_2)(a_1 + a_2)$. I read in a chapter related to quadratic residues and nonresidues that unique prime factorization now tells us that $p$ divides $a_1 −…
-3
votes
1 answer

propositional logic question from GATE2017-2-11

Let p,q,r denote the statements ”It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by? my answer:…
jt26
  • 3
  • 1
-3
votes
3 answers

probability logic

A notebook contains only hundred statements as under: 1 . This notebook contains 1 false statement. 2 . This notebook contains 2 false statements . . . . 99 . This notebook contains 99 false statements. 100. This notebook contains…
Harry
  • 33
-4
votes
1 answer

Propostional Functions

Let $P$ stand for the set of people and let $p \in P$. $C(p)$ is a propositional function that is true when person $p$ plays cricket; $R(p)$ is a propositional function that is true when $p$ plays rugby; and $F(p)$ is true when $p$ plays football.…
Jay
  • 339
1 2 3
30
31