In propositional logic, a formula in Conjunctive Normal Form (CNF) is termed as "glimsy" if for every integer j ≥ 1, any group of j conjuncts contains a propositional variable that is seen only once among those conjuncts. When counting occurrences of propositional variables among a group of conjuncts, the presence of the variable in its negated or non-negated state is immaterial; both are considered. For illustration: Consider the formula (p ∨ q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬s). This is termed as glimsy. On analyzing, if you pick j = 1, each conjunct has a propositional variable that is singular in its occurrence (in actuality, every variable in the conjunct is unique). The repetition in other conjuncts is irrelevant for a specific conjunct's evaluation. For j = 2, choosing conjuncts p ∨ q and q ∨ ¬r, p and r are singular in their occurrences. This holds true for other combinations of two conjuncts as well. Lastly, for j = 3, including all the three conjuncts, p and s occur only once, making the condition true. However, the formula (p ∨ q) ∧ (q ∨ ¬r) ∧ (¬p ∨ ¬r) ∧ (p ∨ ¬s) isn't glimsy. Although some groups of conjuncts meet the criteria, the first three conjuncts together contain p, q, and r twice, and no other variable, violating the glimsy definition. Can we prove by induction that a glimsy formula in CNF using a maximum of m variables comprises at most m conjuncts and is valid?
In propositional logic, a formula in Conjunctive Normal Form (CNF) is termed as "glimsy" if for every integer j ≥ 1, any group of j conjuncts contains a propositional variable that is seen only once among those conjuncts. When counting occurrences of propositional variables among a group of conjuncts, the presence of the variable in its negated or non-negated state is immaterial; both are considered.
For illustration:
Consider the formula (p ∨ q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬s). This is termed as glimsy.
On analyzing, if you pick j = 1, each conjunct has a propositional variable that is singular in its occurrence (in actuality, every variable in the conjunct is unique). The repetition in other conjuncts is irrelevant for a specific conjunct's evaluation. For j = 2, choosing conjuncts p ∨ q and q ∨ ¬r, p and r are singular in their occurrences. This holds true for other combinations of two conjuncts as well. Lastly, for j = 3, including all the three conjuncts, p and s occur only once, making the condition true.
However, the formula (p ∨ q) ∧ (q ∨ ¬r) ∧ (¬p ∨ ¬r) ∧ (p ∨ ¬s) isn't glimsy.
Although some groups of conjuncts meet the criteria, the first three conjuncts together contain p, q, and r twice, and no other variable, violating the glimsy definition.
Can we prove by induction that a glimsy formula in CNF using a maximum of m variables comprises at most m conjuncts and is valid?
![](/static/compass_v2/shared-icons/check-mark.png)
Step by step
Solved in 6 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
This proof is incorrect, as part of the quesiton, it is possible.
Look at the first example:
(p ∨ q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬s).
Both p & ¬s are unique, and satisfy glimsy.
![Advanced Engineering Mathematics](https://www.bartleby.com/isbn_cover_images/9780470458365/9780470458365_smallCoverImage.gif)
![Numerical Methods for Engineers](https://www.bartleby.com/isbn_cover_images/9780073397924/9780073397924_smallCoverImage.gif)
![Introductory Mathematics for Engineering Applicat…](https://www.bartleby.com/isbn_cover_images/9781118141809/9781118141809_smallCoverImage.gif)
![Advanced Engineering Mathematics](https://www.bartleby.com/isbn_cover_images/9780470458365/9780470458365_smallCoverImage.gif)
![Numerical Methods for Engineers](https://www.bartleby.com/isbn_cover_images/9780073397924/9780073397924_smallCoverImage.gif)
![Introductory Mathematics for Engineering Applicat…](https://www.bartleby.com/isbn_cover_images/9781118141809/9781118141809_smallCoverImage.gif)
![Mathematics For Machine Technology](https://www.bartleby.com/isbn_cover_images/9781337798310/9781337798310_smallCoverImage.jpg)
![Basic Technical Mathematics](https://www.bartleby.com/isbn_cover_images/9780134437705/9780134437705_smallCoverImage.gif)
![Topology](https://www.bartleby.com/isbn_cover_images/9780134689517/9780134689517_smallCoverImage.gif)