Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

2
votes
1answer
30 views

Proposition into spoken language

Given: $\sim( p \leftrightarrow (q \vee r) )$ $p:$ It's raining $q:$ The sun is shining $r:$ There are clouds in the sky. Translate the proposition into spoken language. ...
3
votes
6answers
128 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...
4
votes
11answers
409 views

Propositional logic problem about a conversation of four people who lie or tell the truth

This is obviously elementary but can't figure it out. I am taking a course named Logic and Introduction to Analysis next semester and wanted to do some reading beforehand but to figure out how deep ...
3
votes
3answers
81 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
1
vote
1answer
30 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
4answers
84 views

deductions in a propositional calculus

Hope you're all doing well. I have a question about deductions in logical systems. Say we have a logic in the language of propositional logic. We can think of this as the set of tautologies of ...
0
votes
1answer
41 views

How to prove validity of following sequent [closed]

How to prove validity of following: Premises: $p\rightarrow q$, $s\rightarrow t$, Conclusion: $(p \lor s) \rightarrow (q\land t)$
-6
votes
1answer
39 views

Logical argument [on hold]

Let A, B, and C be propositions. Let ∧ denote logical AND, let ∨ denote logical OR, and let ¬ denote logical NOT. Argue that if (𝐴∨𝐵) ∧(¬𝐵∨𝐶) is true, then (𝐴 ∨𝐶) must be true as well.
3
votes
2answers
48 views

How to prove the following using direct proof

$[(\sim p \vee q) \wedge p ] \Rightarrow q $ What should be done next in order to apply direct proof to the example above? The following process has been already done but seemingly it's incorrect: ...
2
votes
3answers
43 views

Indirect proof , odd and even numbers

"Show by indirect proof that if 5n + 3 is an even number then n is an odd number" How could this be solved? I guess I'm in the right track but I don't know how to conclude.
0
votes
1answer
29 views

Readings on more general/abstract notions of induction related to logic

Can someone suggest references to understand the more general/abstract concept of induction? Specifically, I am trying to justify to myself what is called induction on the "complexity of a ...
0
votes
1answer
15 views

Conversion of disjunctive normal form to conjunctive normal form

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.
0
votes
2answers
83 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
1
vote
2answers
231 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
0
votes
1answer
18 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
1
vote
2answers
49 views

Validity in propositional calculus.

I have read some of the answers on similar questions but I can't really get my head around this. So, here are 2 questions I need to answer. Show using a truth table: That the inference ...
10
votes
7answers
7k views

Not understanding this row of truth table for logical implication

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
1
vote
1answer
60 views

Thinking logically instead of Venn diagrams

I hit upon the following identity while reading the book How to Prove: $$(A \cup B) \backslash B \subseteq A$$ Now if I solve this logically I can reduce this like this: $$ \begin{gather*} x \in (A ...
1
vote
2answers
118 views

Is the following sentence a tautology: $(p\Rightarrow q)\vee(r \Rightarrow p)\vee(r\Rightarrow s)\vee(r\Rightarrow q)$?

If both $p$ and $q$ are false then ($p\Rightarrow q$) is true. If either $p$ or $q$ is true then one of ($r\Rightarrow p$) or ($r\Rightarrow q$) is true. If both $p$ and $q$ are true then all are ...
0
votes
2answers
53 views

If “If $A$, then $B$ and not $C$” is true, then is “If $A$ and $C$, then not $B$” true?

Suppose "If $A$, then $B$ and not $C$" is true. Is the following statement true? If $A$ and $C$, then not $B$. I know the answer is true but I don't know the basis behind it.
0
votes
3answers
43 views

Find an equivalent to $(p\lor q) \to (p \lor r)$

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $(p\lor q) \to (p \lor r)$ Thanks in advance for help.
1
vote
1answer
338 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
2answers
36 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
0
votes
2answers
50 views

How to find the equivalent formulas of $\neg ((p\land q) \to (p \land r))$ [closed]

I have following formula: $\neg ((p\land q) \to (p \land r))$ I need to find equivalent formulas of above expression. Thanks in advance for the help.
6
votes
1answer
63 views

Unique decomposition of wffs when left and right parentheses are indistinguishable

I'm working through Enderton's book A Mathematical Introduction to Logic 2nd Edition for self study. Section 1.3 Exercise 7 Suppose that left and right parentheses are indistinguishable. Thus, ...
3
votes
1answer
33 views

Why is the assumption needed in this conditional introduction?

In the first derivation detailed here, why must we include a subderivation with $P$ as an assumption? We can derive $Q$ (4) from $S \land Q$ (2) without the help of $P$ (3); and then since we have ...
0
votes
0answers
67 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
0
votes
1answer
21 views

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 ...
0
votes
2answers
62 views

Can There Get Found Single Axioms for Some Subsystems of Propositional Calculus?

I use Polish notation. All systems have detachment and uniform substitution as the only primitive rules of the system. A user named John told me in an answer "On the question of a single axiom, the ...
3
votes
2answers
37 views

Forming up Complex logical forms from simple one

This is another problem I have been working from Velleman's How to prove book. Let P stand for the statement “I will buy the pants” and S for the statement “I will buy the shirt.” What English ...
7
votes
5answers
1k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
2
votes
1answer
48 views

Simplifying ambiguous statements

I have been working on the following question from Velleman's How to prove book: Let S stand for the statement “Steve is happy” and G for “George is happy.” What English sentences are ...
0
votes
3answers
48 views

Logical form of Either and Neither: Alice in room

This is one of the problem I have been working: ...
1
vote
2answers
38 views

Method of verifying answers

I have been reading Velleman's How to prove it book and solving problems of the exercise in it. What concerns me is that I cannot verify if actually my solutions are correct. The book has only ...
1
vote
0answers
18 views

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ...
-1
votes
2answers
68 views

Creating Truth tables [closed]

What is the truth table for the logical expression? $$ (p \land (p \to q) \land r) \to ((p \lor q) \to r) $$ Frankly, I'm lost.
2
votes
2answers
1k views

Tautology Proof without truth table

How would I go about proving this without a truth table? $[(p \lor q) \implies r ] \implies [ \neg r \implies (\neg p \land \neg q)]$
-1
votes
1answer
95 views

Simplification of boolean expressions

Question 1 $$\begin{align*}A'BC + AB'C + ABC + A'B'C' &=A'B C + B' C (A +A') + ABC\\ &=A'B + C + B'C + ABC \end{align*}$$ Question 2 $$\begin{align*}A'B + B'C + CB &=A'B + C(B +B')\\ ...
2
votes
1answer
30 views

Does introduction and elimination rule for an operator determine uniquely its truth table?

My question is regarding the inference of a truth table for an operator given how it behaves according to introduction and elimination. This follows from an exercise I read, and it got me thinking if ...
1
vote
1answer
43 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
0
votes
4answers
189 views

Logic Confusing Problem

I Read one logic book, can my two conclusion are true? 1- Suppose for each valuation v, we have such n that can we say we have such n that 2- Suppose for each ...
0
votes
1answer
44 views

Relation between an unsatisfiable set and a tautology

In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A ...
1
vote
2answers
37 views

Reducing $ab' + cb + ac$ to $ab' + cb$

Boolean expressions $I = ab' + cb + ac$ and $J = ab' + cb$ have the same truth table. Then why expression $I$ can't be reduced to expression $J$?
6
votes
7answers
3k views

Associativity of logical connectives

According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator? The implies ...
4
votes
1answer
106 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
1
vote
1answer
34 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
0
votes
2answers
74 views

Is it always a tautology?

If any two compound propositions $P$ and $Q$ are equivalent, then is the proposition formed from their biconditional $P \leftrightarrow Q$ always a tautology?
3
votes
2answers
110 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
1
vote
1answer
93 views

Prove that the disjunctions of all conjucts is a disjunctive normal form

Question: I am attempting the following exercise from An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof by Peter B. Andrews: X1408. Prove that if $\mathbf{A}$ is a wff ...
1
vote
1answer
34 views

Correctly understanding truth table problem?

I'm typing up a solution set for an "intro to proof" course. One of the problems asks the student to "construct a truth table for $(P \implies Q) \implies (\neg P)$." I interpreted this as requesting ...